A镇的主街是由N个小写字母构成,镇长准备在上面贴瓷砖,瓷砖一共有M种,第i种上面有Li个小写字母,瓷砖不能旋转也不能被分割开来,瓷砖只能贴在跟它身上的字母完全一样的地方,允许瓷砖重叠,并且同一种瓷砖的数量是无穷的。
问街道有多少字母(地方)不能被瓷砖覆盖。
第一行输入街道长度N(1<=N<=300,000)。
第二行输入N个英文小写字母描述街道的情况。
第三行输入M(1<=M<=5000),表示瓷砖的种类。
接下来M行,每行描述一种瓷砖,长度为Li(1<=Li<=5000),全部由小写字母构成。
输出有多少个地方不能被瓷砖覆盖。
输入1: 6 abcbab 2 cb cbab
输入2: 4 abab 2 bac baba
输入3: 6 abcabc 2 abca cab
输出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); }