字符串匹配算法在实际工程中经常遇到，是各大公司笔试、面试的常考题目。此算法通常输入为原字符串（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 longusing 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;elsecout<<str[i];}cout<<endl;return 0;}