字符串匹配算法
串a ： adbababaaabbaaarbabaaaaaaaaaaabbbhdavgdbebeubdaadjbekagfd 长度：n
串b ： aaaaaaaabbbhdavgdbeb 长度：m
问 ： a串是否含有b串
1）暴力匹配，两重循环，O（n*m）
2）KMP匹配
b串第i个字符与a串第k个字符匹配，用fail数组进行匹配，若失败，b串退到第fail[i-1]+1个字符，直到能匹配成功或退到第一个字符。这个过程中k是不会后退。时间复杂度0(n+m)。
bool KMP(char *T, char *P) { //T=a串，p=b串
int fail[MAXN], match = -1;
getFail(P, fail);
for (int i = 0; T[i]; ++i) {
while (match >= 0 && P[match + 1] != T[i]) {
match = fail[match];
}
if (P[match + 1] == T[i]) { //判断一下是匹配成功跳出，还是退到底了跳出
match++;
if (!P[match + 1]) {
return true;
}
}
}
return false;
}
fail数组 ： kmp算法核心
举个例子：
。。。如果上面没看懂，可以看这个，如果q字符匹配失败，则退到第4个字符a字符再与其匹配
求fail数组，其实就是自己和自己进行KMP匹配。
void getFail(char *P, int *fail) { int match = -1; fail[0] = -1; for (int i = 1; P[i]; ++i) { while (match >= 0 && P[match + 1] != P[i]) {
match = fail[match]; } if (P[match + 1] == P[i]) {
match++; } fail[i] = match; //得到fail值 } }
可以看出从fail数组中得到最直观的信息是子串与原串前缀的重复
原文：http://www.cnblogs.com/lnu161403214/p/7896282.html
