AC自动机模板——贴瓷砖

自动机模板——贴瓷砖"/>

AC自动机模板——贴瓷砖

先上题目：

Description：

A镇的主街是由N个小写字母构成，镇长准备在上面贴瓷砖，瓷砖一共有M种，第i种上面有Li个小写字母，瓷砖不能旋转也不能被分割开来，瓷砖只能贴在跟它身上的字母完全一样的地方，允许瓷砖重叠，并且同一种瓷砖的数量是无穷的。

问街道有多少字母(地方)不能被瓷砖覆盖。

Input

第一行输入街道长度N(1<=N<=300,000)。

第二行输入N个英文小写字母描述街道的情况。

第三行输入M(1<=M<=5000)，表示瓷砖的种类。

接下来M行，每行描述一种瓷砖，长度为Li(1<=Li<=5000)，全部由小写字母构成。

Output

输出有多少个地方不能被瓷砖覆盖。

Sample Input

输入1：
6
abcbab
2
cb
cbab

输入2：
4
abab
2
bac
baba

输入3：
6
abcabc
2
abca
cab

Sample Output

输出1：
2

输出2：
4

输出3：
1

题解：

这是道裸题，需要根据题目要求打优化。
在这道题中，我们需要知道fail链上第一个是单词结尾的点，因此记录一个up数组来优化。最后处理线段覆盖。
注意到有5000*5000=25000000个点，似乎爆掉了，这就是这道题的恶心之处了，需要用一个技巧：能开多大开多大。

Code：

#include<cstdio>
#include<string>
#include<cstdlib>
#include<cstring>
#define fo(i,x,y) for(int i=x;i<=y;i++)
using namespace std;const int N=301000,M=5010;
int tot=1,fail[M*1000],next[M*800][26],count[M*1000],dep[M*1000],up[M*1000];
int d[M*1000],ans0,ans[N][2],bz[N];
int n,m;
char str[N],str2[M];void insert(char *str) {int len=strlen(str), k=1;fo(i,0,len-1) {int x=str[i]-'a';if(next[k][x] == 0)next[k][x] = ++tot, dep[tot] = dep[k] + 1;k=next[k][x];}count[k] ++;
}void build_ac_automation() {int l=0,r=0; d[++r]=1;while(l < r) {int x=d[++l];fo(i,0,25) {int y=next[x][i];if(y != 0) {int z=fail[x];while(z != 0 && next[z][i] == 0)z=fail[z];fail[y]=next[z][i]; if(fail[y] == 0) fail[y]=1;up[y]=y; if(count[y] == 0 && y !=1) up[y]=up[fail[y]];d[++r]=y;}}}
}void query() {int k=1, len=strlen(str);fo(i,0,len - 1) {int x=str[i]-'a';while(k != 1 && next[k][x] == 0) k=fail[k];k=next[k][x]; if(k == 0) k=1;ans[++ans0][0]=i+1; ans[ans0][1]=dep[up[k]];}   
}int main() {scanf("%d", &n);scanf("%s",str);scanf("%d", &m);fo(i,1,m)scanf("%s",str2),insert(str2);build_ac_automation();query();fo(i,1,ans0)bz[ans[i][0]+1] -- , bz[ans[i][0] - ans[i][1] + 1] ++;int tmp=0, pri=0;fo(i,1,n)tmp+=bz[i],pri+=tmp == 0;printf("%d",pri);
}