190709-sugar-AC自动机/dp

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<string>
 4 #include<cstring>
 5 #include<algorithm>
 6 using namespace std;
 7 namespace Moxing{
 8     const int N=5e6+50,inf=0x3f3f3f3f;
 9     char b[N],s[N];
10     int c[N][2],fail[N],q[N],mi[N],cnt,l,r,len,a[N],f[N],n;
11     void insert(char *s){
12         int len=strlen(s),now=0;
13         for(int i=0;i<len;i++){
14             int x=s[i]-‘0‘;
15             if(!c[now][x]) c[now][x]=++cnt;
16             now=c[now][x];
17         }
18         mi[now]=len;
19     }
20     void build(){
21         for(int i=0;i<2;i++){
22             if(c[0][i]) q[++r]=c[0][i];
23         }
24         l=1;
25         while(l<=r){
26             int x=q[l++];
27             for(int i=0;i<2;i++){
28                 int &y=c[x][i];
29                 if(!y) y=c[fail[x]][i];
30                 else fail[y]=c[fail[x]][i],q[++r]=y,mi[y]=min(mi[y],mi[c[fail[x]][i]]);
31             }
32         }
33     } 
34     void ask(char *s){
35         int now=0;len=strlen(s+1);
36         for(int i=1;i<=len;i++){
37             int x=s[i]-‘0‘;
38             now=c[now][x];a[i]=mi[now];
39         } 
40     }
41     struct main{
42         main(){
43             memset(mi,0x3f,sizeof(mi));
44             scanf("%d%s",&n,b+1);
45             for(int i=1;i<=n;i++){
46                 scanf("%s",s),insert(s);
47             }
48             build(),ask(b);
49             for(int i=1;i<=len;i++){
50                 f[i]=f[i-1];
51                 if(a[i]!=inf) f[i]=max(f[i],f[i-a[i]]+1); 
52             }
53             printf("%d",f[len]);
54             exit(0);
55         }
56     }UniversalLove;
57 }
58 int main(){
59     Moxing::main();
60 }
61 //5
62 //010101010111
63 //101
64 //01
65 //11
66 //1000
67 //1110
68 //mi数组记的是now=i时最小的len，a就是串上这个位置作为末尾能匹配到的最短的串的长度
69 //ask函数把now=i时最小的len转换到串的位置上