字符串在显示生活中，用的较多，有必要学习字符串的匹配算法。字符串匹配算法大概有4种，分别是：朴素算法，Rabin-Karp算法，有限自动机算法，Kunth-Morris-Pratt。
一 朴素算法
朴素字符串匹配算法是通过双重循环找到所有匹配的子串，对n-m+1个可能的偏移进行检查，n为文本串的长度，m为模式串的长度。该算法容易理解，不用进行预处理，匹配的复杂度是O（(n-m+1)m）。
参考代码：
#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;
bool naive_string_matcher (string T, string P){
int n = T.size ();
int m = P.size ();
for (int s = 0; s <= n - m; s++){
bool ok = true;
for (int i = 0; i < m;i++)
if (P[i] != T[s + i]){
ok = false;
break;
}
if (ok)return true;
}
return false;
}
int main (){
string t = "abcdefg";
string p = "cde";
cout << naive_string_matcher (t, p) << endl;
system ("pause");
return 0;
}
二 Rabin-karp算法
实际中使用能够很好的运行。
算法描述：将每个字符赋予响应的权值，在匹配的时候首先检查模式串和子串的权值是否相等，如果不等，则检查下一个位置；如果相等，则检测子串是否相同。预处理的时间为O(m)。
这里会存在一个问题，如果子串的权值过大，无法表示的问题，假如用0-25表示26个字母的权值，如果子串的长度较长（其实实际中不会太长），无法表示。这个时候该怎么办？可以使用同余的知识，选择一个较大的素数p，对子串的权值进行模p操作，这样如果两个子串的权值w1！=w2(mod p)，两个字符串一定不同，但是如果w1=w2(mod p)，并不能说明w1=w2，需要进行进一步的检测。