KMP算法
<pre><code class="language-cpp">#include <iostream>
#include <string>
using namespace std;
const int maxn = 1e5+5;
int Next[maxn];
void GetNext(const string &p){
int p_len = p.size();
int i = 0;
int j = -1;
Next[i] = -1;
while(i < p_len){
if(j == -1 || p[i] == p[j]){
i++;
j++;
if(p[i] != p[j]) Next[i] = j;
else Next[i] = Next[j];
}
else j = Next[j];
}
return;
}
int KMP(const string &s, const string &p){
GetNext(p);
int i = 0;
int j = 0;
int s_len = s.size();
int p_len = p.size();
while(i < s_len && j < p_len){
if(j == -1 || s[i] == p[j]){
i++;
j++;
}
else j = Next[j];
}
if(j == p_len) return i - j;
else return -1;
}</code></pre>