换了个模板。
O(n)复杂度求P串出现在T串中的所有位置。
void getFail(char* P, int* f) { int m = strlen(P); f[0] = 0; f[1] = 0; for(int i = 1; i < m; i++) { int j = f[i]; while(j && P[i] != P[j]) { j = f[j]; } f[i + 1]=P[i]==P[j]?j+1:0; } } int find(char* T, char*P, int*f) { int n = strlen(T), m = strlen(P); getFail(P, f); int j = 0; for(int i = 0; i < n; i++) { while(j && P[j] != T[i]) { j = f[j]; } if(P[j] == T[i]) { j++; } if(j == m) { return i - m + 1; } } return -1; }