1 string str;
2 int next[N];// 核♥: next[k] 字符串前(k-1)个元素有next[k]个相等前后缀
3 // 初始化 next[0]=-1; next[1]=0;
4 void get_next() {
5 int k=-1;
6 int i=0;
7 next[0]=-1;
8 int len=str.size();
9 while (i<len) {
10 if (k==-1||str[k]==str[i]) next[++i]=++k;
11 else k=next[k];
12 }
13 return ;
14 }
15 int find (string s,string t) {
16 int n1=s.size();
17 int n2=t.size();
18 int i,j;
19 i=j=0;
20 while (i<n1&&j<n2) {
21 if (j==-1||s[i]==t[j]){
22 i++;
23 j++;
24 }
25 else j=next[j];
26 }
27 if (j==n2) return i-n2;
28 else return -1;
29 }