【COCI2012】覆盖字符串

【题目描述】

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

【题解】

很魔性的一道题，一看就知道是AC自动机，这里有个小优化，插入时判断一下：如果模式串是文本的子串就插入。

然后就转化为了线段覆盖问题。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<ctime>
 7 #include<algorithm>
 8 using namespace std;
 9 #define MAXN 2500010
10 int n,m,cnt,ans,v[MAXN],q[MAXN],fail[MAXN],k[MAXN],tr[1000100][27],vis[27][27][27][27][27];
11 char b[MAXN],ch[5010];
12 inline int read()
13 {
14     int x=0,f=1;  char ch=getchar();
15     while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
16     while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
17     return x*f;
18 }
19 void insert(int p)
20 {
21     int now=0;
22     for(int i=1;i<=p;i++)
23     {
24         if(!tr[now][ch[i]]) tr[now][ch[i]]=++cnt;
25         now=tr[now][ch[i]];
26     }
27     v[now]=p;
28 }
29 void build()
30 {
31     int head=0,tail=0;
32     for(int i=0;i<26;i++)  if(tr[0][i])  q[++tail]=tr[0][i];
33     while(++head<=tail)
34     {
35         int x=q[head];
36         for(int i=0;i<26;i++)
37         {
38             int y=tr[x][i];
39             if(!y) continue;
40             q[++tail]=y;
41             int temp=fail[x];
42             while(temp&&!tr[temp][i])  temp=fail[temp];
43             fail[y]=tr[temp][i];
44         }
45     }
46 }
47 void work()
48 {
49     for(int i=1,x=0;i<=n;i++)
50     {
51         while(x&&!tr[x][b[i]]) x=fail[x]; x=tr[x][b[i]];  int temp=x;
52         while(temp) {if(v[temp]) k[i-v[temp]+1]=v[temp];  temp=fail[temp];}
53     }
54     for(int i=1,last=0;i<=n;i++)
55     {
56         if(k[i])  last=max(last,k[i]+i-1);
57         if(last<i)  ans++;
58     }
59     printf("%d
",ans);
60 }
61 int main()
62 {
63     //freopen("cin.in","r",stdin);
64     //freopen("cout.out","w",stdout);
65     n=read();  scanf("%s",b+1);
66     for(int i=1;i<=n;i++)  b[i]=b[i]-'a';
67     for(int i=5;i<=n;i++)  vis[b[i]][b[i-1]][b[i-2]][b[i-3]][b[i-4]]=1;
68     m=read();
69     for(int i=1;i<=m;i++)  
70     {
71         scanf("%s",ch+1);  bool flag=0;  int len=strlen(ch+1);
72         for(int j=1;j<=len;j++)  ch[j]=ch[j]-'a';
73         for(int j=5;j<=len;j++)  if(!vis[ch[j]][ch[j-1]][ch[j-2]][ch[j-3]][ch[j-4]]) {flag=1;break;}
74         if(!flag)  insert(len);
75     }
76     build();
77     work();
78     return 0;
79 }

【COCI2012】覆盖字符串

相关推荐