题意：

先给你一个不超过1000000长度的大串s；接下来输入一个n代表接下来输入的小串个数，小串长度不超过6。

小串分两种类型0和1类型。

0类型表示小串在大串中的最大匹配个数就是常规的AC自动机的做法。

1类型表示小串在大串中不能重合的最大匹配数。

依次输出结果.（所有的串只包含小写字母）

按样例输出，注意每组测试数据后有一个换行。

题意我不想写了抄的， （不好意思啦）

 

0 类型的就是最开始的模板题

1 类型的处理方式就是，在建立字典树的时候弄一个dep数组，记录每一个节点的深度

然后在query的过程中查询上一个单词最后一个字母出现的位置。

if (i - last[temp] >= dep[temp]) ans[temp][1]++, last[temp] = i;

这样就可以了。

 

1 #include 
      
         2 #include 
       

Q; 87 fail[root] = root; 88 for (int i = 0; i < 26; i++) 89 if (next[root][i] == -1) next[root][i] = root; 90 else { 91 fail[next[root][i]] = root; 92 Q.push(next[root][i]); 93 } 94 while (!Q.empty()) { 95 int now = Q.front(); 96 Q.pop(); 97 for (int i = 0; i < 26; i++) 98 if (next[now][i] == -1) next[now][i] = next[fail[now]][i]; 99 else {100 fail[next[now][i]] = next[fail[now]][i];101 Q.push(next[now][i]);102 }103 }104 }105 106 void query(char buf[]) {107 int len = strlen(buf);108 int now = root;109 mem(ans,0);110 mem(last, -1);111 for (int i = 0; i < len; i++) {112 now = next[now][buf[i] - 'a'];113 int temp = now;114 while (temp != root) {115 ans[temp][0]++;116 if (i - last[temp] >= dep[temp]) ans[temp][1]++, last[temp] = i;117 temp = fail[temp];118 }119 }120 }121 122 void debug() {123 for (int i = 0; i < cnt; i++) {124 printf("id = %3d,fail = %3d,end = %3d,chi = [", i, fail[i], End[i]);125 for (int j = 0; j < 26; j++) printf("%2d", next[i][j]);126 printf("]\n");127 }128 }129 } ac;130 131 int main() {132 // FIN;133 int cas = 1;134 while (~sfs(buf)) {135 ac.init();136 sfi(n);137 for (int i = 0; i < n; ++i) {138 scanf("%d%s", &vis[i], str[i]);139 pos[i] = ac.insert(str[i]);140 }141 ac.build();142 ac.query(buf);143 printf("Case %d\n", cas++);144 for (int i = 0; i < n; ++i) printf("%d\n", ans[pos[i]][vis[i]]);145 printf("\n");146 }147 return 0;148 }