KMP
http://www.matrix67.com/blog/archives/115
注意这个从1开始字符串，从0开始不好写，不过不优化fail的从0还是好写- -！
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <iostream>
5 using namespace std;
6 #define maxn 1000005
7 int n, m, k;
8 int a[maxn],fail[maxn];
9 char str1[maxn], str2[maxn];
10 void init(){
11 int j = 0;
12 for (int i = 2; i <= m; i++){
13 while (j&&str2[i] != str2[j + 1])j = fail[j];
14 if (str2[i] == str2[j + 1])j++;
15 fail[i] = j;
16 }
17 }
18 void kmp(){
19 int j = 0; k = 0;
20 for (int i = 1; i <= n; i++){
21 while (j&&str1[i] != str2[j + 1])j = fail[j];
22 if (str1[i] == str2[j + 1])j++;
23 if (j == m){ a[k++] = i - m + 1; j = fail[j]; }
24 }
25 }
26 int main(){
27 while (~scanf("%s%s", str1+1, str2+1)){
28 n = strlen(str1 + 1);
29 m = strlen(str2 + 1);
30 init();
31 kmp();
32 for (int i = 0; i < k; i++)printf(i==k-1?"%d\n":"%d ", a[i]);
33 }
34 return 0;
35 } View Code
AC自动机
http://wenku.baidu.com/link?url=_WLP8BEXP8hSTvQPl_drqiSeOkkEkno0LveEwD5ZRSSb5zolHaV6kVXoELIdrxpWriPjL_O6od4FrMWvpB5dPcX28qbQ0BOd5nBCagt4IN_
首先要把深度为i之前的fail指针求出来才能求深度为i的fail指针，BFS刚好符合！
最后没看懂的再看看下面的这个回答
某某:我把我的想法说下`是不是`对 ``你最后的那个trie先在要求的是she中h的失败指针，而对``h深度`h-1的失败指针都已经求出来（可以通过归纳证明）所以
对h只要沿着它父亲走失败指针的看失败指针指向的节点是否有一个 儿子和h 相等，而由失败指针的定义。h以上有n个和失败指针到 root之间
匹配，所以 如果找到一个h 说明有n+1个匹配 得证。 希作者看到后联系我- - 看我的理解对不对``还是有更加具体化的思路我没有想到```
这种代码肯定会被各种卡的，知道写，乱改就可以了。。。我都懒得去知道以前写的了
1 #include <cstdio>
2 #include <cstring>
3 #include <queue>
4 #include <algorithm>
5 #include <iostream>
6 using namespace std;
7 #define maxn 1005005
8 #define sz_ 26
9 int n, k, t, sz, cnt;
10 int m[10005];
11 int q[maxn];
12 int ch[maxn][sz_];
13 int fail[maxn];
14 vector<int>g[10005],val[maxn];
15 char str1[maxn], str2[105];
16 void insert(char *str, int v){
17 int u = 0, len = strlen(str+1);
18 for (int i = 1; i <= len; i++){
19 int c = str[i] - \'a\';
20 if (!ch[u][c]){
21 memset(ch[sz], 0, sizeof ch[sz]);
22 val[sz].clear();
23 ch[u][c] = sz++;
24 }
25 u = ch[u][c];
26 }
27 val[u].push_back(v);
28 }
29 void bfs(){
30 int u = 0;
31 int head=0,tail=0;
32 for (int i = 0; i < sz_; i++){
33 int v = ch[u][i];
34 if (v){ fail[v] = 0; q[tail++] = v; }
35 }
36 while (head!=tail){
37 int u = q[head++];
38 for (int i = 0; i < sz_; i++){
39 int v = fail[u];
40 if (!ch[u][i])continue;
41 q[tail++] = ch[u][i];
42 while (v&&!ch[v][i])v = fail[v];
43 fail[ch[u][i]] = ch[v][i];
44 }
45 }
46 }
47 void ac(){
48 int u = 0;
49 for (int i = 1; i <= n; i++){
50 int c = str1[i] - \'a\';
51 while (u&&!ch[u][c])u = fail[u];
52 u=ch[u][c];
53 int ux = u;
54 while (ux){
55 for (int j = 0; j < val[ux].size(); j++)
56 g[val[ux][j]].push_back(i - m[val[ux][j]] + 1);
57 ux = fail[ux];
58 }
59 }
60 }
61 int main(){
62 while (~scanf("%s", str1 + 1)){
63 n = strlen(str1 + 1);
64 scanf("%d", &k);
65 cnt = 0;
66 sz = 1; memset(ch[0], 0, sizeof ch[0]);
67 for (int i = 0; i <= 10004; i++)g[i].clear();
68 for (int i = 1; i <= k; i++){
69 scanf("%s", str2 + 1);
70 m[i] = strlen(str2 + 1);
71 insert(str2, i);
72 }
73 bfs();
74 ac();
75 for (int i = 1; i <= k; i++)cnt+=g[i].size();
76 printf("%d\n", cnt);
77 for (int i = 1; i <= k; i++)
78 for (int j = 0; j < g[i].size(); j++)
79 printf(j == g[i].size() - 1 ? "%d\n" : "%d ", g[i][j]);
80 for (int i = 0; i <= sz; i++)val[i].clear();
81 }
82 return 0;
83 } View Code
