字符串匹配算法在实际工程中经常遇到，是各大公司笔试、面试的常考题目。此算法通常输入为原字符串（string）和子串（pattern），要求返回子串在原字符串中首次出现的位置。比如原字符串为“ABCDEFG”，子串为“DEF”，则算法返回3。常见的算法包括BF（Brute Force，暴力检索）、RK（Robin-Karp，哈希检索）、KMP（教科书上最常见的算法）、BM（Boyer Moore）、Sunday等。

01、实例分析：潜伏者

问题描述:

R国和 S 国正陷入战火之中，双方都互派潜伏者（间谍），潜入对方内部，伺机行动。历尽艰险后，潜伏于 S 国的 R 国间谍小 C 终于摸清了 S 国军用密码的编码规则:

(1) S 国军方内部欲发送的原信息经过加密后在网络上发送，原信息的内容与加密后所得的内容均由大写字母‘A’～‘Z’构成（无空格等其他字符）。

(2) S 国对每个字母规定了对应的“密字”。加密的过程就是将原信息中的所有字母替换为其对应的“密字”。

(3) 每个字母只对应一个唯一的“密字”，不同的字母对应不同的“密字”。“密字”可以和原字母相同。

例如，若规定‘A’的密字为‘A’，‘B’的密字为‘C’（其他字母及密字略），则原信息“ABA”被加密为“ACA”。

现在，小 C 通过内线掌握了 S 国网络上发送的一条加密信息及其对应的原信息。小 C希望能通过这条信息破译S国的军用密码。小C的破译过程是这样的: 扫描原信息，对于原信息中的字母X（代表任一大写字母），找到其在加密信息中的对应大写字母Y，并认为在密码里Y是X的密字。如此进行下去，直到停止于如下的某个状态:

(1) 所有信息扫描完毕，‘A’～‘Z’所有26个字母在原信息中均出现过并获得了相应的“密字”。

(2) 所有信息扫描完毕，但发现存在某个（或某些）字母在原信息中没有出现。

(3) 扫描中发现掌握的信息里有明显的自相矛盾或错误（违反 S 国密码的编码规则）。例如，某条信息“XYZ”被翻译为“ABA”就违反了“不同字母对应不同密字”的规则。

在小 C 忙得头昏脑涨之际，R 国司令部又发来电报，要求他翻译另外一条从 S 国刚刚截取到的加密信息。现在请你帮助小 C: 通过内线掌握的信息尝试破译密码，然后利用破译的密码翻译电报中的加密信息。

输入格式:

共3行，每行为一个长度在1～100的字符串。

第1行为小C掌握的一条加密信息。

第2行为第1行的加密信息所对应的原信息。

第3行为R国司令部要求小C翻译的加密信息。

输入数据保证所有字符串仅由大写字母‘A’～‘Z’构成，且第1行长度与第2行长度相等。

输出格式:

共1行。

若破译密码停止时出现（2）和(3)两种情况，则输出Failed（首字母大写，其他小写），否则输出利用密码翻译电报中加密信息后得到的原信息。

输入样例#1:

输出样例:

输入样例:

输出样例:

 输入样例:

输出样例:

输入输出样例1说明:

原信息中的字母‘A’和‘B’对应相同的密字，输出Failed。

输入输出样例2说明:

字母‘Z’在原信息中没有出现，输出Failed。

思路:

(1) A～Z必须都存在，否则输出Failed。

(2) 密文中的每个字母不能给多个字母使用，否则输出Failed。

参考程序:

#include<iostream>
#include<cstring>
using namespace std;
char map[26];
int main()
{
string secret,original,translation;
int len1,len3;
int i,j;
cin>>secret>>original>>translation; ;//输人密文、原文、要翻译的文字
len1=secret.length() ;  //计算密文长度
len3=translation.length(); //计算要翻译的文字长度
if(len1<26)  //若密文长度小于 26 个字母的长度，则不合要求,输出 Eailed,终止程序
}
{
cout<<"Failed"<<endl;
return 0;
}
for(i=0;i<lenl;i++)
{
for(j=0;j<i;j++)
if(original[i]==original[jl&&secret[il!=secret[j]) //若原文中有相同字母,但密文中对应字母不相同,则不合要求,输出 Eailed,终止
//程序
{
cout<<"Failed"<<endl;
return 0;
}
map[secret[il-'A']=original[i];   //存储密文对应的原文 
}
for(i=0;i<len3;i++)  //输出翻译后的文字
cout<<map[translation[i]-'A'];
cout<<end1;
return 0;    
}

02、实例分析：最低三元字符串
问题描述:

给定一个三元字符串(该字符串仅由字符'0'、'1'和'2'组成)。

可以交换任意两个相邻(连续)字符'0'和'1'(即将"01"替换为"10"，反之亦然) 或任何两个相邻(连续)字符“1”及“2”(即将“12”替换为“21”，反之亦然)。例如，对于字符串“010210”，可以执行以下步骤。

“010210”→→ “100210”;

“010210” →→ “001210”;

“010210” →→ “010120”;

“010210” →→ “010201”。

例如，对于字符串“010210”，可以执行以下操作: 注意不能将“02”转换为“20”，反之亦然。除上面描述的以外，不能使用给定字符串执行其他任何操作。

你的任务是通过使用这些交换任意次数(可能为零)获得可能的最小值(字典上的)字符串。

如果存在位置i(1≤i≤|a|，其中|s|是字符串"ss"的长度)，则字符串"aa"在字典上小于字符串"bb"(如果字符串"aa"和"bb"有相同的长度)，使得对于每一个j<i< span="">，都有aj=bj, ai<bi< span="">。

输入:

输入的第一行包含仅由'0'、'1'和'2'组成的字符串"s"，其长度为1～105(含105)。

输出:

打印一个字符串——通过使用上面描述的交换可以获得的最小字符串(字典上的)次数(可能为零)。

输入样例:

100210
输出样例:

001120
输入样例:

11222121
输出样例:

11112222
输入样例:

20
输出样例:

20
题意: 给出一串只有0、1、2的数串，其中，0与1可互相交换，1与2可互相交换，求交换后最小的值。

思路: 无论1在哪，总能被换到2的前面，但0无法换到2的前面，因此先统计第一个2前面0的个数，输出；然后再统计整个数串中1的个数，输出；最后再将第一个2后面的所有数字去掉1后输出。

参考程序:

#include<iostream>
#include<cstdio>
#include<cstring>
# include< cmath>
#include<algorithm>
#include<string>
# include<cstdlib>
# include<queue>
# include< set>
# include<map>
#include<stack>
#include<ctime>
#include<vector>
#define INF Ox3f3f3f3f
# define PI acos(-1.0)
#define N 1001
#define MOD 10007
#define E 1e-6
# define LL long long
using namespace std;
int main()
{
string str;
cin>>str;
LL len=str.length() ;
LI num 1=0;
bool flag=true;
for(LL i=0;i<len;i++)
if(str[il=='1')num 1++;
if(str[i]=='1' str[i]=='2')
flag=false;
LL pos;
LI num 0=0;
for(LL i=0;i<len;i++)
f(str[i]=='0')
num 0++;
if(str[i]=='2')
pos=i;
break;
if(flag)
cout<<str<<endl;
return 0;
}
while(num 0--)
cout<<'0';
while(num 1--)
cout<<'1';
for(LL i=pos;i<len;i++)
{
if(str[il=='1')
continue;
else
cout<<str[i];
}
cout<<endl;
return 0;
}