简单的说，就是对主串的每一个字符作为字串的开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开头做字串的长度的小循环，直到匹配成功或者全部遍历为止。
让我们来分析一下，最好的情况是什么？那就是第一开始就成功，时间时间复杂度为O(1) ；最坏呢，就是每次循环到子串最后一位才发现不对，时间复杂度为O((n-m+1)*m)
效率确实太低
于是就有了下面的算法
避免不必要的回溯
比如 a = "abcabcabc" t = "abcabx"
循环到 j = 6 时发现错误，这时t中，有两个ab，如果按朴素模式的化此时 j = 2；但是，刚才我们已经遍历过 a[2] = t[2] = b 不可能再等于 t[2] ,要避免这多余的回溯，如果 j 应该等于3
应该t中 t[1-2] = t[4-5] 而第 6为失败，说明检测第6位时应该跳过t[1-2] 使得 j = 3；
abcabcabc
abcabx
abcabx 从c开始匹配
这时就需要一个next[] 数组来记录 j 该是什么
next[j] = 1 到 j-1 中 前缀 和 后缀 相同字母的个数+1
下面是 构造next数组的代码： ///尽力了。。
void GetNext(string s,int next[]) { next[0] = -1; int len = s.length(); int i = 0;//s 的下标 int j = -1; while(i<len) { if(s[i]==s[j]||j==-1)//最大前缀后缀公共字串长度为j， //那么比较此为和第j+1位字符是否相同，j+1位 下标为j { // 相同则最大公共长度+1 i++; j++; next[i] = j; } else// 不同 则 找 和前j项 能组成的最大公共长度， //而前j项最大字串为next[j] 则判断第next[j]+1项和i是否相同， //next[j]+1项的下标为next[j] { j = next[j]; } } }
KMP函数就比较简单 和朴素算法相同 只是 小循环 回溯时发生了变化
int KMP(string s,string p,int next[]) { GetNext(p,next); int i = 0; int j = 0; int slen = s.length(); int plen = p.length(); while(i<slen&&j<plen) { if(j==-1||s[i]==p[j]) // j = -1 表示第一个就不匹配,则比较下一个 // ||当字符相同时比较下一个 { i++; j++; } else { j = next[j];// 注意next[0] = -1 需要特判 } } if(j==plen) { return i-j; } else { return -1; } }
完整代码
#include<iostream> #include<string> #include<cstring> using namespace std; void GetNext(string s,int next[]) { next[0] = -1; int len = s.length(); int i = 0;//s 的下标 int j = -1; while(i<len) { if(s[i]==s[j]||j==-1)//最大前缀后缀公共字串长度为j， //那么比较此为和第j+1位字符是否相同，j+1位 下标为j { // 相同则最大公共长度+1 i++; j++; next[i] = j; } else// 不同 则 找 和前j项 能组成的最大公共长度， //而前j项最大字串为next[j] 则判断第next[j]+1项和i是否相同， //next[j]+1项的下标为next[j] { j = next[j]; } } } int KMP(string s,string p,int next[]) { GetNext(p,next); int i = 0; int j = 0; int slen = s.length(); int plen = p.length(); while(i<slen&&j<plen) { if(j==-1||s[i]==p[j]) // j = -1 表示第一个就不匹配,则比较下一个 //||当字符相同时比较下一个 { i++; j++; } else { j = next[j]; } } if(j==plen) { return i-j; } else { return -1; } } int main() { string s,p; cin>>s; cin>>p; int next[100]={0}; int flag = KMP(s,p,next); cout<<flag<<endl; return 0; }
原文：https://www.cnblogs.com/subject/p/12379876.html
