[coci2012]覆盖字符串 AC自动机

给出一个长度为N的小写字母串，现在Mirko有M个若干长度为Li字符串。现在Mirko要用这M个字符串去覆盖给出的那个字符串的。覆盖时，必须保证：
1.Mirko的字符串不能拆开，旋转；
2.Mirko的字符串必须和给出的字符串的某一连续段完全一致才能覆盖，
3.若干次覆盖可以部分重叠
4.Mirko的字符串可以无限使用。
求给出的字符串当中，有多少个字母是无法覆盖的。

小朋友们，作为一名长者，我认为我有必要向你们传授一些人生的经验~；

字符串的一堆函数，慎用慎用；

本人只因没有仔细认真，把strlen(s),strlen(ch)之类的函数写在了循环的里面，造成了无限TLE的惨剧；

图如下：

两个strlen在里面的时候：

#01: Accepted (15ms, 322696KB)
#02: Accepted (15ms, 322696KB)
#03: Accepted (187ms, 322696KB)
#04: Accepted (3234ms, 322696KB)
#05: Accepted (3453ms, 322624KB)
#06: Time Limit Exceeded (?, 322624KB)
#07: Time Limit Exceeded (?, 322624KB)
#08: Time Limit Exceeded (?, 322624KB)
#09: Time Limit Exceeded (?, 322624KB)
#10: Time Limit Exceeded (?, 322624KB)
#11: Time Limit Exceeded (?, 322624KB)
#12: Wrong Answer (5000ms, 322624KB)
#13: Wrong Answer (5000ms, 322624KB)
#14: Time Limit Exceeded (?, 322624KB)
#15: Time Limit Exceeded (?, 322624KB)
#16: Time Limit Exceeded (?, 322624KB)
#17: Wrong Answer (5000ms, 322624KB)
#18: Wrong Answer (5000ms, 322624KB)
#19: Time Limit Exceeded (?, 322624KB)

不知道的会以为我暴力枚举；

一个strlen在循环里的时候：

#01: Accepted (15ms, 345056KB)
#02: Accepted (0ms, 345056KB)
#03: Accepted (0ms, 345056KB)
#04: Accepted (218ms, 345056KB)
#05: Accepted (78ms, 345056KB)
#06: Accepted (93ms, 345056KB)
#07: Accepted (46ms, 345056KB)
#08: Accepted (1656ms, 345056KB)
#09: Time Limit Exceeded (?, 345056KB)
#10: Accepted (93ms, 344984KB)
#11: Accepted (125ms, 344984KB)
#12: Accepted (1562ms, 344984KB)
#13: Time Limit Exceeded (?, 344984KB)
#14: Accepted (171ms, 344984KB)
#15: Accepted (500ms, 344984KB)
#16: Accepted (1640ms, 344984KB)
#17: Wrong Answer (5000ms, 344984KB)
#18: Accepted (250ms, 344984KB)
#19: Accepted (734ms, 344984KB)

还是有三组超了；

没有strlen在里面的时候：

#01: Accepted (0ms, 357712KB)
#02: Accepted (0ms, 357712KB)
#03: Accepted (15ms, 357712KB)
#04: Accepted (78ms, 357712KB)
#05: Accepted (93ms, 357712KB)
#06: Accepted (46ms, 357712KB)
#07: Accepted (46ms, 357712KB)
#08: Accepted (375ms, 357712KB)
#09: Accepted (187ms, 357712KB)
#10: Accepted (93ms, 357712KB)
#11: Accepted (31ms, 357712KB)
#12: Accepted (359ms, 357712KB)
#13: Accepted (328ms, 357712KB)
#14: Accepted (187ms, 357712KB)
#15: Accepted (125ms, 357712KB)
#16: Accepted (359ms, 357712KB)
#17: Accepted (468ms, 357712KB)
#18: Accepted (281ms, 357712KB)
#19: Accepted (140ms, 357712KB)

敲完这道题，我热泪盈眶啊；

同时，我通过这道题敲了好几遍AC自动机模板；

代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<cstdlib>

 #include<ctime>

 #include<vector>

 #include<algorithm>

 #include<queue>

 #include<map>

 using namespace std;

 #define LL long long

 const int maxn=;

 int n,m;

 char s[],ch[];

 bool vis[][][][][];

 int linkk[][],flag[maxn],f[maxn],q[maxn],g[maxn],k[maxn],tail=,head=,len=,next[maxn];

 void insert(){

     int now=,p=strlen(ch);

     for(int i=;i<p;i++){

         if(!linkk[now][ch[i]])linkk[now][ch[i]]=++len,g[len]=ch[i];

         now=linkk[now][ch[i]];

         if(i==p-)flag[now]=p;

     }

 }

 void init(){

     //printf("first:%d\n",clock());

     scanf("%d%s%d",&n,s,&m);

     for(int i=;i<n;i++)s[i]=s[i]-'a'+;

     for(int i=;i<n;i++)vis[s[i-]][s[i-]][s[i-]][s[i-]][s[i]]=;

     //printf("second:%d\n",clock());

     for(int i=;i<=m;i++){

         scanf("%s",ch);

         bool p=;

         int u=strlen(ch);

         for(int j=;j<u;j++)ch[j]=ch[j]-'a'+;

         for(int j=;j<u;j++)

             if(!vis[ch[j-]][ch[j-]][ch[j-]][ch[j-]][ch[j]]){p=;break;}

         if(!p)insert();

     }

     //printf("init:%d\n",clock());

 }

 void bfs(){

     head=,tail=;q[++tail]=;int x=,now=,temp;

     while(++head<=tail){

         x=q[head];

         for(int i=;i<=;i++){

             if(linkk[x][i]){

                 now=linkk[x][i],temp=f[x];

                 if(x){

                     while(temp&&!linkk[temp][i])temp=f[temp];

                     f[now]=linkk[temp][i];

                     if(flag[f[now]])next[now]=f[now];

                     else next[now]=next[f[now]];

                 }

                 q[++tail]=now;

             }

         }

     }

 }

 void work(){

     bfs();

     //printf("bfs:%d\n",clock());

     int now=;

     for(int i=;i<n;i++){

         if(!linkk[now][s[i]]){

             int temp=f[now];

             while(!linkk[temp][s[i]]&&temp)temp=f[temp];

             now=linkk[temp][s[i]];

         }

         else now=linkk[now][s[i]];

         int temp=now;

         while(temp){

             if(flag[temp])k[i-flag[temp]+]=flag[temp];

             temp=next[temp];

         }

     }

     //printf("work:%d\n",clock());

     int last=-,sum=;

     for(int i=;i<n;i++){

         if(k[i])last=max(last,k[i]+i-);

         if(i>last)sum++;

     }

     cout<<sum<<endl;

     //cout<<clock()<<endl;

 }

 int main(){

     freopen("1.in","r",stdin);

     freopen("1.out","w",stdout);

     init();

     work();

 }

巴特西

[coci2012]覆盖字符串 AC自动机

最新文章

热门文章