int kmp(string S, string T) { // write code here int n = S.length(); int m = T.length(); int N = 5e5+10; int ne[N]; int cnt=0; ne[0] = 0; //ne数组求解 for(int i=1, j=0; i<n; i++) { while(j && S[j]!=S[i]) j = ne[j-1]; if(S[j]==S[i]) j++; ne[i]=j; } //匹配模板链 for(int i=0, j=0; i<=m; i++) { while(j && S[j]!=T[i]) j = ne[j-1]; if(S[j]==T[i]) j++; if(j==n) { cnt++; j = ne[j-1]; } } return cnt;