1、朴素法
#include <iostream> using namespace std; const int N = 100010, M = 1000010; int n, m; int ne[N]; char s[M], p[N]; int main() { cin >> n >> p + 1 >> m >> s + 1; for (int i = 2, j = 0; i <= n; i ++ ) { while (j && p[i] != p[j + 1]) j = ne[j]; if (p[i] == p[j + 1]) j ++ ; ne[i] = j; } for (int i = 1, j = 0; i <= m; i ++ ) { while (j && s[i] != p[j + 1]) j = ne[j]; if (s[i] == p[j + 1]) j ++ ; if (j == n) { printf("%d ", i - n); j = ne[j]; } } return 0; }
这个过程其实很简单,就是将数组从前往后遍历,同时产生next数组,每次不从零开始检索,而是利用next数组,从next开始匹配,next由最大前缀和最小前缀决定。