AC自动机入门

Aho-Corasick automaton，该算法在1975年产生于贝尔实验室，是著名的多模式匹配算法之一。

KMP算法很好的解决了单模式匹配问题，如果有了字典树的基础，我们可以完美的结合二者解决多模式匹配问题。

在KMP算法中，我们预先根据待匹配串自身的信息得到失配指针，使得在每次匹配不成功后，可以不再去处理模式串的已匹配过的部分，进而使得复杂度降为O（N）。

对于多模式串匹配问题，当一个模式串与待匹配串不匹配时，失配指针可以指向任意一个串，这就需要我们利用字典树来组织所有模式串并得到失配指针。

构造失配指针的详细过程可参考 http://blog.csdn.net/niushuai666/article/details/7002823

时间复杂度分析：假设有N个长不超过m的模式串，待匹配串长度为L。建字典树的复杂度为O（Nm），对于每个L的前缀，最坏情况下匹配树高（m）次，故总的复杂度为O（（N+L）*m）。

我的模板

 1 /*
 2 基于HDOJ 2222 的 AC自动机
 3 文本串对多个模板串的查找
 4 */
 5 #include<bits/stdc++.h>
 6 using namespace std;
 7 const int maxn = 555555;
 8 const int alp =26;
 9 
10 int ch[maxn][alp], ed[maxn], fail[maxn];
11 char str[1001000];
12 
13 int root, sz;
14 
15 int newnode()
16 {
17     memset(ch[sz], -1, sizeof(ch[sz]));
18     ed[sz] = 0;
19     return sz++;
20 }
21 void init()
22 {
23     sz = 0;
24     root = newnode();
25 }
26 void Insert(char str[])
27 {
28     int len = strlen(str);
29     int now = root;
30     for(int i=0; i<len; i++)
31     {
32         int &tmp = ch[now][str[i]-'a'];
33         if(tmp == -1) tmp = newnode();
34         now = tmp;
35     }
36     ed[now] ++;
37 }
38 
39 
40 void build()
41 {
42     queue<int> q;
43     fail[root] = root;
44     for(int i=0; i<alp; i++)
45     {
46         int &tmp = ch[root][i];
47         if(tmp == -1) tmp = root;
48         else fail[tmp] = root, q.push(tmp);
49     }
50     while(!q.empty())
51     {
52         int now = q.front(); q.pop();
53         for(int i=0; i<alp; i++)
54         {
55             int &tmp = ch[now][i];
56             if(tmp == -1) tmp = ch[fail[now]][i];
57             else fail[tmp] = ch[fail[now]][i], q.push(tmp);
58         }
59     }
60 }
61 
62 int query(char str[])
63 {
64     int len = strlen(str);
65     int now = root;
66     int ret = 0;
67     for(int i=0; i<len; i++)
68     {
69         int tmp = now = ch[now][str[i]-'a'];
70         while(tmp != root)
71         {
72             if(ed[tmp] > 0)
73                 ret += ed[tmp],
74                 ed[tmp] = 0;
75             tmp = fail[tmp];
76         }
77     }
78     return ret;
79 }
80 
81 int main()
82 {
83     int n, t;
84     scanf("%d",&t);
85     while(t--)
86     {
87         scanf("%d",&n);
88         init();
89         for(int i=1; i<=n; i++)
90             scanf("%s",str), Insert(str);
91         build();
92         scanf("%s",str);
93         printf("%d
",query(str));
94     }
95     return 0;
96 }

View Code

入门练习题 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=96376#overview

1. hdu 2896 病毒侵袭

　　字典树的节点标记模式串的编号即可，注意字符的ASCALL码在128以内。

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int maxn = 111111;
  4 const int alp = 128;
  5 
  6 int ch[maxn][alp], ed[maxn], fail[maxn];
  7 char str[10100];
  8 
  9 int root, sz;
 10 
 11 int newnode()
 12 {
 13     memset(ch[sz], -1, sizeof(ch[sz]));
 14     ed[sz] = 0;
 15     return sz++;
 16 }
 17 void init()
 18 {
 19     sz = 0;
 20     root = newnode();
 21 }
 22 void Insert(char str[], int tag)
 23 {
 24     int len = strlen(str);
 25     int now = root;
 26     for(int i=0; i<len; i++)
 27     {
 28         int &tmp = ch[now][str[i]];
 29         if(tmp == -1) tmp = newnode();
 30         now = tmp;
 31     }
 32     ed[now] = tag;
 33 }
 34 
 35 void build()
 36 {
 37     queue<int> q;
 38     fail[root] = root;
 39     for(int i=0; i<alp; i++)
 40     {
 41         int &tmp = ch[root][i];
 42         if(tmp == -1) tmp = root;
 43         else fail[tmp] = root, q.push(tmp);
 44     }
 45     while(!q.empty())
 46     {
 47         int now = q.front(); q.pop();
 48         for(int i=0; i<alp; i++)
 49         {
 50             int &tmp = ch[now][i];
 51             if(tmp == -1) tmp = ch[fail[now]][i];
 52             else fail[tmp] = ch[fail[now]][i], q.push(tmp);
 53         }
 54     }
 55 }
 56 
 57 bool vis[510];
 58 
 59 void query(char str[])
 60 {
 61     int len = strlen(str);
 62     int now = root;
 63     int ret = 0;
 64     for(int i=0; i<len; i++)
 65     {
 66         int tmp = now = ch[now][str[i]];
 67         while(tmp != root)
 68         {
 69             if(ed[tmp]) vis[ed[tmp]] = 1;
 70             tmp = fail[tmp];
 71         }
 72     }
 73 }
 74 
 75 int main()
 76 {
 77     int n, m;
 78     while(scanf("%d",&n) == 1)
 79     {
 80         init();
 81         for(int i=1; i<=n; i++)
 82             scanf("%s",str), Insert(str, i);
 83         build();
 84         scanf("%d",&m);
 85         int total = 0;
 86         for(int i=1; i<=m; i++)
 87         {
 88             memset(vis, 0, sizeof(vis));
 89             scanf("%s",str);
 90             query(str);
 91             int a[5], id = 0;
 92             for(int j=1; j<=n; j++)
 93                 if(vis[j]) a[++id] = j;
 94             if(id) {
 95                 printf("web %d:",i);
 96                 for(int j=1; j<=id; j++) printf(" %d", a[j]);
 97                 puts("");
 98                 total++;
 99             }
100         }
101         printf("total: %d
",total);
102     }
103     return 0;
104 }

View Code

2. hdu 3065 病毒侵袭持续中

　　由于所找的串允许重叠，那就恰好是AC自动机模板了，在Trie上查找时，只要该节点有标记，加上即可。待匹配串的除大写字母以外的可见字符是没有用的，统一更改为'Z'+1就行了。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 111111;
 4 const int alp = 27;
 5 
 6 int ch[maxn][alp], ed[maxn], fail[maxn];
 7 char str[2000100];
 8 int num[1010];
 9 
10 int root, sz;
11 
12 int newnode()
13 {
14     memset(ch[sz], -1, sizeof(ch[sz]));
15     ed[sz] = 0;
16     return sz++;
17 }
18 void init()
19 {
20     sz = 0;
21     root = newnode();
22 }
23 void Insert(char str[], int tag)
24 {
25     int len = strlen(str);
26     int now = root;
27     for(int i=0; i<len; i++)
28     {
29         int &tmp = ch[now][str[i]-'A'];
30         if(tmp == -1) tmp = newnode();
31         now = tmp;
32     }
33     ed[now] = tag;
34 }
35 
36 void build()
37 {
38     queue<int> q;
39     fail[root] = root;
40     for(int i=0; i<alp; i++)
41     {
42         int &tmp = ch[root][i];
43         if(tmp == -1) tmp = root;
44         else fail[tmp] = root, q.push(tmp);
45     }
46     while(!q.empty())
47     {
48         int now = q.front(); q.pop();
49         for(int i=0; i<alp; i++)
50         {
51             int &tmp = ch[now][i];
52             if(tmp == -1) tmp = ch[fail[now]][i];
53             else fail[tmp] = ch[fail[now]][i], q.push(tmp);
54         }
55     }
56 }
57 
58 void query(char str[])
59 {
60     int len = strlen(str);
61     int now = root;
62     int ret = 0;
63     for(int i=0; i<len; i++)
64     {
65         int tmp = now = ch[now][str[i]-'A'];
66         while(tmp != root)
67         {
68             if(ed[tmp])  num[ed[tmp]] ++;
69             tmp = fail[tmp];
70         }
71     }
72 }
73 char s[1010][55];
74 int main()
75 {
76     int n, m;
77     while(scanf("%d",&n) == 1)
78     {
79         init();
80         for(int i=1; i<=n; i++)
81             scanf("%s",s[i]), Insert(s[i], i), num[i]=0;
82         build();
83         scanf("%s",str);
84         for(int i=0; str[i]; i++)
85             if(str[i]<'A' || str[i] >'Z') str[i] = 'Z'+1;
86         query(str);
87         for(int i=1; i<=n; i++)
88             if(num[i])
89             printf("%s: %d
",s[i], num[i]);
90     }
91     return 0;
92 }

View Code

3. zoj 3430 Detect the Virus

　　恶心+AC自动机，以后写

4.poj 2778 DNA Sequence

　　给N(N<=10)个长度不超过10的DNA串，问可以构造出多少个长度为M（M<=2000000000)的DNA串不含以上串，所有串仅由'A'、'C'、'G'、'T'四个字符构成。

对于一个有向图，我们要求一点x到另一点y的长度为L不同路径的个数，构造一个矩阵，令mat[i][j]表示直接相连i和j的边的数量，那么该矩阵的L次幂的mat[x,y]就是答案。

　　这里我们可以先构造出最多101个节点的Trie图，建立AC自动机，标记给出的串。对于每个节点u，并枚举每个以上字符，若该节点没被标记并且转移后的节点v也没有被标记，那么mat[u][v]++。求出pow(mat,M)，矩阵第一行之和就是答案，因为它代表从root（空串）开始所有的长度为M的满足要求的所有串的数量和。

　　*注意，对于串"A"和"TAG",在建立自动机时，对于串"TAG"中的'A'节点也应该被标记，也就是说，每个节点的标记要考虑到失配节点的标记。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<queue>
  7 typedef long long LL;
  8 using namespace std;
  9 const int maxn = 111111;
 10 const int N = 110;
 11 const int alp = 4;
 12 const LL mod = 100000;
 13 int ch[maxn][alp], ed[maxn], fail[maxn];
 14 char str[20];
 15 int Hash['z'];
 16 int root, sz;
 17 void mul(LL a[N][N], LL b[N][N])
 18 {
 19     LL c[N][N] = {0};
 20     for(int k=0; k<sz; k++)
 21         for(int i=0; i<sz; i++)
 22             for(int j=0; j<sz; j++)
 23             c[i][j] = (c[i][j] + a[i][k]*b[k][j]) % mod;
 24     memcpy(a, c, sizeof(c));
 25 }
 26 void quick_mod(LL a[N][N], int b)
 27 {
 28     LL c[N][N] = {0};
 29     for(int i=0; i<sz; i++) c[i][i] = 1;
 30     while(b)
 31     {
 32         if(b&1) mul(c,a);
 33         mul(a, a);
 34         b>>=1;
 35     }
 36     memcpy(a, c, sizeof(c));
 37 }
 38 
 39 int newnode()
 40 {
 41     memset(ch[sz], -1, sizeof(ch[sz]));
 42     ed[sz] = 0;
 43     return sz++;
 44 }
 45 void init()
 46 {
 47     sz = 0;
 48     root = newnode();
 49 }
 50 void Insert(char str[])
 51 {
 52     int len = strlen(str);
 53     int now = root;
 54     for(int i=0; i<len; i++)
 55     {
 56         int &tmp = ch[now][Hash[str[i]]];
 57         if(tmp == -1) tmp = newnode();
 58         now = tmp;
 59     }
 60     ed[now] = 1;
 61 }
 62 
 63 void build()
 64 {
 65     queue<int> q;
 66     fail[root] = root;
 67     for(int i=0; i<alp; i++)
 68     {
 69         int &tmp = ch[root][i];
 70         if(tmp == -1) tmp = root;
 71         else fail[tmp] = root, q.push(tmp);
 72     }
 73     while(!q.empty())
 74     {
 75         int now = q.front(); q.pop();
 76         for(int i=0; i<alp; i++)
 77         {
 78             int &tmp = ch[now][i];
 79             if(tmp == -1) tmp = ch[fail[now]][i];
 80             else fail[tmp] = ch[fail[now]][i], ed[tmp] |= ed[fail[tmp]], q.push(tmp);
 81         }
 82     }
 83 }
 84 
 85 void get_matrix(LL a[N][N])
 86 {
 87     for(int i=0; i<sz; i++)
 88     {
 89         if(ed[i]) continue;
 90         for(int j=0; j<4; j++)
 91         {
 92             if(ed[ch[i][j]]) continue;
 93             a[i][ch[i][j]] ++;
 94         }
 95     }
 96 }
 97 
 98 int main()
 99 {
100     int n, m;
101     Hash['A'] = 0, Hash['C'] = 1, Hash['G'] = 2, Hash['T'] = 3;
102     while(scanf("%d %d",&n,&m) == 2)
103     {
104         init();
105         for(int i=1; i<=n; i++)
106         {
107             scanf("%s",str);
108             Insert(str);
109         }
110         build();
111         LL a[N][N] = {0};
112         get_matrix(a);
113         quick_mod(a, m);
114         LL ans = 0;
115         for(int i=0; i<sz; i++)
116             ans =(ans + a[0][i]) % mod;
117         printf("%I64d
",ans);
118     }
119     return 0;
120 }

View Code

5.hdu 2243 考研路茫茫——单词情节

　　求长度不超过m的至少包含一个所给模式串的串的个数，并对2^64取模。

假设长度只能为m,上题中我们计算了不包含模式串的串的个数，而串的总数为pow(26,m)，包含模式串的串的个数就是两者只差，这是很容易得出的。
那么如何求出所有长度不超过m的串的总数呢？
对于前者，我们对上题的矩阵的边长加1，并且置最后一列全为1，这样，矩阵的第一行之和就记录了所有情况之和，由于初始第一行最后一列为1，结果减一即可。
对于后者，令sum_pow(26,x)表示26^1+26^2+26^3+...+26^x, 则有，若x为奇数转化为26^x+sum_pow(26,x-1), 若为偶数则转化为sum_pow(26,x/2)*(26^(x/2)+1),这样可在log(x)内的时间复杂度内求出。
对于模2^64,只要将所有结果保存为unsigned long long 型，自然溢出就相当于对2^64取模。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<queue>
  7 using namespace std;
  8 typedef unsigned long long ull;
  9 const int N = 50;
 10 const int alp = 26;
 11 const int maxn = 555555;
 12 int ch[maxn][alp], ed[maxn], fail[maxn];
 13 int root, sz;
 14 
 15 int newnode()
 16 {
 17     memset(ch[sz], -1, sizeof(ch[sz]));
 18     ed[sz++] = 0;
 19     return sz-1;
 20 }
 21 void init()
 22 {
 23     sz = 0;
 24     root = newnode();
 25 }
 26 
 27 void Insert(char str[])
 28 {
 29     int len = strlen(str);
 30     int now = root;
 31     for(int i=0; i<len; i++)
 32     {
 33         int &tmp = ch[now][str[i]-'a'];
 34         if(tmp == -1) tmp = newnode();
 35         now = tmp;
 36     }
 37     ed[now] = 1;
 38 }
 39 
 40 void build()
 41 {
 42     queue<int> q;
 43     fail[root] = root;
 44     for(int i=0; i<alp; i++)
 45     {
 46         int &tmp = ch[root][i];
 47         if(tmp == -1) tmp = root;
 48         else fail[tmp] = root, q.push(tmp);
 49     }
 50     while(!q.empty())
 51     {
 52         int now = q.front(); q.pop();
 53         for(int i=0; i<alp; i++)
 54         {
 55             int &tmp = ch[now][i];
 56             if(tmp == -1) tmp = ch[fail[now]][i];
 57             else fail[tmp] = ch[fail[now]][i],
 58                  ed[tmp] |= ed[fail[tmp]],
 59                  q.push(tmp);
 60         }
 61     }
 62 }
 63 
 64 void get_matric(ull a[N][N])
 65 {
 66     for(int i=0; i<sz; i++)
 67     {
 68         if(ed[i]) continue;
 69         for(int j=0; j<alp; j++)
 70         {
 71             if(ed[ch[i][j]]) continue;
 72             a[i][ch[i][j]] ++;
 73         }
 74     }
 75     for(int i=0; i<=sz; i++) a[i][sz] = 1;
 76 }
 77 
 78 ull quick_mod(ull a, ull b)
 79 {
 80     ull c = 1;
 81     while(b) {
 82         if(b&1) c = c * a;
 83         a = a * a;
 84         b >>= 1;
 85     }
 86     return c;
 87 }
 88 ///pow(a,1)+pow(a,2)+...+pow(a,x);
 89 ull sum_pow(ull a, ull x)
 90 {
 91     if(x == 1) return a;
 92     if(x&1) return quick_mod(a,x) + sum_pow(a, x-1);
 93     return sum_pow(a, x>>1) * (quick_mod(a, x>>1)+1);
 94 }
 95 void mul(ull a[N][N], ull b[N][N])
 96 {
 97     ull c[N][N] = {0};
 98     for(int k=0; k<=sz; k++)
 99         for(int i=0; i<=sz; i++)
100             for(int j=0; j<=sz; j++)
101             c[i][j] += a[i][k]*b[k][j];
102     memcpy(a, c, sizeof c);
103 }
104 void mat_pow(ull a[N][N], ull b)
105 {
106     ull c[N][N] = {0};
107     for(int i=0; i<=sz; i++)
108         c[i][i] = 1;
109     while(b){
110         if(b&1) mul(c, a);
111         mul(a, a);
112         b >>= 1;
113     }
114     memcpy(a, c, sizeof c);
115 }
116 
117 char s[12];
118 int main()
119 {
120     int i,j,k;
121     ull n, m;
122     while(scanf("%I64u %I64u",&n,&m) == 2)
123     {
124         init();
125         for(i=1; i<=n; i++) scanf("%s",s), Insert(s);
126         build();
127         ull a[N][N] = {0};
128         get_matric(a);
129         mat_pow(a, m);
130         ull ans = 0;
131         for(i=0; i<=sz; i++) ans += a[0][i];
132         printf("%I64u
",sum_pow(26,m)-ans+1);
133     }
134     return 0;
135 }

View Code

6.poj 1625 Censored!

　　给你一个不超过50的字典，然后还有不超过10个长度不超过50的非法串，问有多少个由字典组成的长度为m的串？没有取模。

我真想喷这题，没有任何思维上的新点，就是恶心+恶心。

1）.卡内存，明显可以按poj 2778的套路，构造500*500矩阵搞就行了，但是，卡内存啊。注意到m不大，那就dp吧，dp[i][j]表示串长为i时在自动机j节点上的合法串的数量，状态转移也很简单：遍历字母表，如果j节点接收某个字符后转移到k节点，那么dp[i][k] += dp[i-1][j]，初始dp[0][0] = 1。

2）.ASCALL可高达255，我用java写的更坑爹，由于java中char是2个字节，有时会把输入的两个字符当成一个字符输入。。好吧，又改成了byte型的才行。

3）.那么到底输入的p个串是由字母表构成的吗？我怎么测出来非法串还有其他字符啊，按照大家的做法，把不在字典中的字符哈希为0就稀里糊涂过了。

真的是够了，出题人的良心呢？

  1 import java.math.BigInteger;
  2 import java.util.Arrays;
  3 import java.util.LinkedList;
  4 import java.util.Queue;
  5 import java.util.Scanner;
  6 
  7 public class Main{
  8     static int alp;
  9     static final int maxn = 505;
 10     static int ch[][] = new int[maxn][55];
 11     static int ed[] = new int[maxn];
 12     static int fail[] = new int[maxn];
 13     static int Hash[] = new int[66666];
 14     static BigInteger dp[][] = new BigInteger[55][maxn];
 15     static int root, sz;
 16     static Queue<Integer> q = new LinkedList<Integer>();
 17     
 18     static int newnode() {
 19         Arrays.fill(ch[sz], -1);
 20         ed[sz++] = 0;
 21         return sz-1;
 22     }
 23     
 24     static void init()
 25     {
 26         sz = 0;
 27         root = newnode();
 28     }
 29     
 30     static void Insert(byte str[]){
 31         int now = root;
 32         for(int i=0; i<str.length; i++) {
 33             int t = str[i];
 34             t += 128;
 35             if(ch[now][Hash[t]] == -1)
 36                 ch[now][Hash[t]] = newnode();
 37             now = ch[now][Hash[t]];
 38         }
 39         ed[now] = 1;
 40     }
 41     
 42     static void build()
 43     {
 44         q.clear();
 45         fail[root] = root;
 46         for(int i=0; i<alp; i++){
 47             if(ch[root][i] == -1) ch[root][i] = root;
 48             else {
 49                 fail[ch[root][i]] = root; q.add(ch[root][i]);
 50             }
 51         }
 52         while(!q.isEmpty()) {
 53             int now = q.remove();
 54             for(int i=0; i<alp; i++)
 55             {
 56                 if(ch[now][i] == -1) ch[now][i] = ch[fail[now]][i];
 57                 else {
 58                     fail[ch[now][i]] = ch[fail[now]][i];
 59                     ed[ch[now][i]] |= ed[fail[ch[now][i]]];
 60                     q.add(ch[now][i]);
 61                 }
 62             }
 63         }
 64     }
 65     static void memset(BigInteger a[][], BigInteger x)
 66     {
 67         for(int i=0; i<a.length; i++) 
 68             for(int j=0; j<a[i].length; j++)
 69                 a[i][j] = x;
 70     }
 71     public static void main(String[] args) {
 72         @SuppressWarnings("resource")
 73         Scanner in = new Scanner(System.in);
 74         int n, m, p;
 75         while(in.hasNext())
 76         {
 77             n = in.nextInt(); m = in.nextInt(); p = in.nextInt(); 
 78             Arrays.fill(Hash, 0);
 79             byte s[] = in.next().getBytes();
 80             for(int i=0; i<n; i++) {
 81                 int t = s[i];
 82                 t += 128;
 83                 Hash[t] = i;
 84             }
 85             init();
 86             alp = n;
 87             for(int i=1; i<=p; i++)
 88             {
 89                 byte str[] = in.next().getBytes();
 90                 Insert(str);
 91             }
 92             build();
 93             memset(dp, BigInteger.ZERO);
 94             dp[0][0] = BigInteger.ONE;
 95             for(int i=1; i<=m; i++)
 96                 for(int j=0; j<sz; j++)
 97                 {
 98                     if(ed[j] > 0) continue;
 99                     for(int k=0; k<n; k++)
100                     {
101                         int tmp = ch[j][k];
102                         if(ed[tmp] > 0) continue;
103                         dp[i][tmp] = dp[i][tmp].add(dp[i-1][j]);
104                     }
105                 }
106             BigInteger ans = BigInteger.ZERO;
107             for(int i=0; i<sz; i++) ans = ans.add(dp[m][i]);
108             System.out.println(ans);
109         }
110     }
111 }

View Code

7.hdu 2825 Wireless Password

　　给m个单词，问长为n的至少包含k个单词的串有多少个？(0<=m<=10, 1<=n<=25)

dp的状态和当前串长、Trie节点、已含单词集有关，那么dp[i][j][k]就表示当前串长为i，在Trie的j节点，状态为k（0<=k<2^10)。初始dp[0][0][0] = 1。

　　有两种转移方式：要么枚举dp[i][j][k]的前一个状态加到dp[i][j][k]，要么枚举dp[i][j][k]的后一个状态，将dp[i][j][k]的值加到后一个状态。

复杂度均为O（25*100*2048*26），但是时限比较紧，我们选择后者方式，如果dp[i][j][k]=0，直接continue,它对后续状态无贡献。再者，数据数较多，不能每次用memset清空dp数组。这样优化后大概就能A掉了。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<queue>
  7 using namespace std;
  8 typedef unsigned long long ull;
  9 const int N = 50;
 10 const int mod = 20090717;
 11 const int alp = 26;
 12 const int maxn = 555;
 13 int ch[maxn][alp], ed[maxn], fail[maxn];
 14 int root, sz;
 15 
 16 int newnode()
 17 {
 18     memset(ch[sz], -1, sizeof(ch[sz]));
 19     ed[sz++] = 0;
 20     return sz-1;
 21 }
 22 void init()
 23 {
 24     sz = 0;
 25     root = newnode();
 26 }
 27 
 28 void Insert(char str[], int id)
 29 {
 30     int now = root;
 31     for(int i=0; str[i]; i++)
 32     {
 33         int &tmp = ch[now][str[i]-'a'];
 34         if(tmp == -1) tmp = newnode();
 35         now = tmp;
 36     }
 37     ed[now] |= 1<<id-1;
 38 }
 39 
 40 void build()
 41 {
 42     queue<int> q;
 43     fail[root] = root;
 44     for(int i=0; i<alp; i++)
 45     {
 46         int &tmp = ch[root][i];
 47         if(tmp == -1) tmp = root;
 48         else fail[tmp] = root, q.push(tmp);
 49     }
 50     while(!q.empty())
 51     {
 52         int now = q.front();
 53         q.pop();
 54         for(int i=0; i<alp; i++)
 55         {
 56             int &tmp = ch[now][i];
 57             if(tmp == -1) tmp = ch[fail[now]][i];
 58             else fail[tmp] = ch[fail[now]][i],
 59                                  ed[tmp] |= ed[fail[tmp]],
 60                                             q.push(tmp);
 61         }
 62     }
 63 }
 64 char str[25];
 65 int dp[26][110][1<<10];
 66 int num[1<<10];
 67 
 68 int solve(int n, int m, int k)
 69 {
 70     for(int i=0; i<=n; i++)
 71         for(int j=0; j<sz; j++)
 72             for(int sta=0; sta<(1<<m); sta++)
 73                 dp[i][j][sta] = 0;
 74     dp[0][0][0] = 1;
 75     /*****************************************
 76     for(int len=1; len<=n; len++)
 77         for(int pre=0; pre<sz; pre++)
 78             for(int sta=0; sta<(1<<m); sta++)
 79     {
 80         for(int a=0; a<alp; a++)
 81         {
 82             int tmp = ch[pre][a];
 83             if(ed[tmp] && !(sta&(1<<ed[tmp]-1))) continue;
 84             int &p = dp[len][tmp][sta];
 85             if(ed[tmp])
 86                 p = (p + dp[len-1][pre][sta]+dp[len-1][pre][sta^(1<<ed[tmp]-1)]) % mod;
 87             else p = (p + dp[len-1][pre][sta])%mod;
 88             if(p > 1000000000) p %= mod;
 89         }
 90     }
 91     *****************************************************/
 92     for(int len=0; len<n; len++)
 93         for(int pre=0; pre<sz; pre++)
 94             for(int sta=0; sta<(1<<m); sta++)
 95             {
 96                 if(dp[len][pre][sta] == 0) continue;
 97                 for(int a=0; a<alp; a++)
 98                 {
 99                     int tmp = ch[pre][a];
100                     int &pp = dp[len+1][tmp][sta|ed[tmp]];
101                     pp += dp[len][pre][sta];
102                     if(pp > 1000000000) pp %= mod;
103                 }
104             }
105     int ans = 0;
106     for(int now=0; now<sz; now++)
107         for(int sta=0; sta<(1<<m); sta++)
108             if(num[sta] >= k)
109             {
110                 ans += dp[n][now][sta];
111                 if(ans > 1000000000) ans %= mod;
112             }
113     return ans%mod;
114 }
115 int main()
116 {
117     int i,j,k,m,n;
118     memset(num, 0, sizeof(num));
119     num[0] = 0, num[1] = 1;
120     for(int i=2; i<(1<<10); i++)
121         num[i] = num[i>>1] + (i&1);
122     while(scanf("%d %d %d",&n,&m,&k) == 3 && n+m+k)
123     {
124         init();
125         for(i=1; i<=m; i++)
126             scanf("%s",str), Insert(str, i);
127         build();
128         printf("%d
",solve(n,m,k));
129     }
130     return 0;
131 }

View Code

8.hdu 2296 Ring

　　给m个单词和长为L的串，问至少需要改变几个字符使得L串不包含任意一个单词。单词50个*20，L<=1000,字母均由'A''C''G''T'组成。

　　令dp[i][j]表示子串s[0,i-1]止于状态j不包含单词所需要改变字符数，初始dp数组inf, dp[0][0] = 0。那么dp[i][j] = min{dp[i-1][k]+(s[i-1] != c) | k由字符c转移到j}。同样，也可以由dp[i][j]来更新dp[i+1][k]，并且加入dp[i][j] != inf优化。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<queue>
  7 using namespace std;
  8 typedef unsigned long long ull;
  9 const int inf = 0x3f3f3f3f;
 10 const int N = 1111;
 11 const int alp = 4;
 12 const int maxn = 555;
 13 int Hash['Z'];
 14 char ALP[4] = {'A','C','G','T'};
 15 int ch[maxn][alp], ed[maxn], fail[maxn];
 16 int root, sz;
 17 
 18 int newnode()
 19 {
 20     memset(ch[sz], -1, sizeof(ch[sz]));
 21     ed[sz++] = 0;
 22     return sz-1;
 23 }
 24 void init()
 25 {
 26     sz = 0;
 27     root = newnode();
 28 }
 29 
 30 void Insert(char str[])
 31 {
 32     int now = root;
 33     for(int i=0; str[i]; i++)
 34     {
 35         int &tmp = ch[now][Hash[str[i]]];
 36         if(tmp == -1) tmp = newnode();
 37         now = tmp;
 38     }
 39     ed[now] = 1;
 40 }
 41 
 42 void build()
 43 {
 44     queue<int> q;
 45     fail[root] = root;
 46     for(int i=0; i<alp; i++)
 47     {
 48         int &tmp = ch[root][i];
 49         if(tmp == -1) tmp = root;
 50         else fail[tmp] = root, q.push(tmp);
 51     }
 52     while(!q.empty())
 53     {
 54         int now = q.front();
 55         q.pop();
 56         for(int i=0; i<alp; i++)
 57         {
 58             int &tmp = ch[now][i];
 59             if(tmp == -1) tmp = ch[fail[now]][i];
 60             else fail[tmp] = ch[fail[now]][i],
 61                 ed[tmp] |= ed[fail[tmp]],
 62                 q.push(tmp);
 63         }
 64     }
 65 }
 66 char str[1100];
 67 int dp[N][maxn];
 68 
 69 void solve()
 70 {
 71     int len = strlen(str);
 72     memset(dp, 0x3f, sizeof(dp));
 73     dp[0][0] = 0;
 74     int now = root;
 75     for(int len=0; str[len]; len++)
 76         for(int pre=0; pre<sz; pre++)
 77     {
 78         if(ed[pre]) continue;
 79         if(dp[len][pre] == inf) continue;
 80         for(int a=0; a<alp; a++)
 81         {
 82             int tmp = ch[pre][a];
 83             if(ed[tmp]) continue;
 84             dp[len+1][tmp] = min(dp[len+1][tmp], dp[len][pre]+(str[len] != ALP[a]));
 85         }
 86     }
 87     int ans = inf;
 88     for(int i=0; i<sz; i++)
 89         if(!ed[i]) ans = min(ans, dp[len][i]);
 90     if(ans == inf) puts("-1");
 91     else printf("%d
",ans);
 92 }
 93 int main()
 94 {
 95     int i,j,k,m,n,t;
 96     int cas = 0;
 97     Hash['A'] = 0, Hash['C'] = 1, Hash['G'] = 2, Hash['T'] = 3;
 98     while(scanf("%d",&n) == 1 && n)
 99     {
100         init();
101         for(i=1; i<=n; i++)
102             scanf("%s",str), Insert(str);
103         build();
104         scanf("%s",str);
105         printf("Case %d: ",++cas);
106         solve();
107     }
108     return 0;
109 }

View Code

9.zoj 3228 Searching the String

　　给一个长串len<=10^5，给N个0/1属性的长度不超过6的字符串，N<=10^5。

　　输出每个串在长串中匹配的个数，属性为0/1分别表示可/不可重叠。

　　对所有小串建立AC自动机，每个节点保留0/1属性串匹配的个数，再记录上一次1串匹配到此处的时间，若匹配到此处找到一串，那么只有时间差大于等于串的长度才能+1并更新此时间。0串完全是模板，直接++即可。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<queue>
  7 using namespace std;
  8 typedef unsigned long long ull;
  9 const int inf = 0x3f3f3f3f;
 10 const int N = 100010;
 11 const int alp = 26;
 12 const int maxn = 666666;
 13 int ch[maxn][alp], ed[maxn][2], fail[maxn];
 14 int Hash[N];
 15 int root, sz;
 16 int tim[maxn], num[maxn][2], len[maxn];
 17 int newnode()
 18 {
 19     memset(ch[sz], -1, sizeof(ch[sz]));
 20     tim[sz] = 0;
 21     ed[sz][0] = ed[sz][1] = 0;
 22     num[sz][0] = num[sz][1] = 0;
 23     return sz++;
 24 }
 25 void init()
 26 {
 27     sz = 0;
 28     root = newnode();
 29 }
 30 
 31 void Insert(char str[], int tag, int id)
 32 {
 33     int now = root, i;
 34     for(i=0; str[i]; i++)
 35     {
 36         int &tmp = ch[now][str[i]-'a'];
 37         if(tmp == -1) tmp = newnode();
 38         now = tmp;
 39     }
 40     Hash[id] = now;
 41     ed[now][tag] = 1;
 42     len[now] = i;
 43 }
 44 
 45 void build()
 46 {
 47     queue<int> q;
 48     fail[root] = root;
 49     for(int i=0; i<alp; i++)
 50     {
 51         int &tmp = ch[root][i];
 52         if(tmp == -1) tmp = root;
 53         else fail[tmp] = root, q.push(tmp);
 54     }
 55     while(!q.empty())
 56     {
 57         int now = q.front();
 58         q.pop();
 59         for(int i=0; i<alp; i++)
 60         {
 61             int &tmp = ch[now][i];
 62             if(tmp == -1) tmp = ch[fail[now]][i];
 63             else fail[tmp] = ch[fail[now]][i],
 64                 q.push(tmp);
 65         }
 66     }
 67 }
 68 
 69 char str[maxn], s[11];
 70 int tag[N];
 71 void solve(int n)
 72 {
 73     int now = root;
 74     for(int i=0; str[i]; i++)
 75     {
 76         int tmp = now = ch[now][str[i]-'a'];
 77         while(tmp != root)
 78         {
 79             if(ed[tmp][0]) {
 80                 num[tmp][0]++;
 81             }
 82             if(ed[tmp][1] && i+1-tim[tmp] >= len[tmp]) {
 83                 num[tmp][1]++;
 84                 tim[tmp] = i+1;
 85             }
 86             tmp = fail[tmp];
 87         }
 88     }
 89     for(int i=1; i<=n; i++)
 90         printf("%d
",num[Hash[i]][tag[i]]);
 91     puts("");
 92 }
 93 
 94 int main()
 95 {
 96     int i,j,k,m,n,t,cas=0;
 97     while(scanf("%s",str) == 1)
 98     {
 99         scanf("%d",&n);
100         init();
101         for(i=1; i<=n; i++)
102         {
103             scanf("%d %s",&m, s);
104             tag[i] = m;
105             Insert(s, m, i);
106         }
107         build();
108         printf("Case %d
",++cas);
109         solve(n);
110     }
111     return 0;
112 }

View Code

10.hdu 3341 RLost's revenge

　　给N个Len<=10的单词，再给一个长不超过40的串，将此串字母位置重置，使得包含最多的单词，N<=50。所有单词仅由字母'A''C''G''T'组成。

　　我们不用考虑输入长串的形态，只记录各个字母的个数就行了。dp很好想，令dp[i][j]表示在自动机i节点，字母的使用情况为j时包含的最多的单词数量。

难点就在于：如何表示'A''C''G''T'的使用情况？

　　假设有num[0]个'A',num[1]个'C',num[2]个'G',num[3]个'T'，那么使用了a个'A'，c个'C'，g个'G'，t个'T'可表示为a*(num[1]+1)*(num[2]+1)*(num[3]+1) + c*(num[2]+1)*num[3]+1) + g*(num[3]+1) + t。字母数均分时最大且<11*11*11*11。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<queue>
  7 using namespace std;
  8 typedef unsigned long long ull;
  9 const int inf = 0x3f3f3f3f;
 10 const int N = 11*11*11*11+5;
 11 const int alp = 4;
 12 const int maxn = 555;
 13 int ch[maxn][alp], ed[maxn], fail[maxn];
 14 int Hash['Z'];
 15 int root, sz;
 16 int newnode()
 17 {
 18     memset(ch[sz], -1, sizeof(ch[sz]));
 19     ed[sz] = 0;
 20     return sz++;
 21 }
 22 void init()
 23 {
 24     sz = 0;
 25     root = newnode();
 26 }
 27 
 28 void Insert(char str[])
 29 {
 30     int now = root, i;
 31     for(i=0; str[i]; i++)
 32     {
 33         int &tmp = ch[now][Hash[str[i]]];
 34         if(tmp == -1) tmp = newnode();
 35         now = tmp;
 36     }
 37     ed[now] ++;
 38 }
 39 
 40 void build()
 41 {
 42     queue<int> q;
 43     fail[root] = root;
 44     for(int i=0; i<alp; i++)
 45     {
 46         int &tmp = ch[root][i];
 47         if(tmp == -1) tmp = root;
 48         else fail[tmp] = root, q.push(tmp);
 49     }
 50     while(!q.empty())
 51     {
 52         int now = q.front();
 53         q.pop();
 54         ed[now] += ed[fail[now]];
 55         for(int i=0; i<alp; i++)
 56         {
 57             int &tmp = ch[now][i];
 58             if(tmp == -1) tmp = ch[fail[now]][i];
 59             else fail[tmp] = ch[fail[now]][i],
 60                  q.push(tmp);
 61         }
 62     }
 63 }
 64 int dp[maxn][N];
 65 char str[44];
 66 int num[4];
 67 void Max(int &a, int b) {a = max(a, b);}
 68 int main()
 69 {
 70     int i,j,k,m,n,t,cas=0;
 71     Hash['A'] = 0, Hash['C']= 1, Hash['G'] = 2, Hash['T'] = 3;
 72     while(scanf("%d",&n) == 1 && n)
 73     {
 74         init();
 75         memset(num, 0, sizeof(num));
 76         for(int i=1; i<=n; i++)
 77             scanf("%s",str), Insert(str);
 78         build();
 79         scanf("%s",str);
 80         for(i=0; str[i]; i++) num[Hash[str[i]]]++;
 81         memset(dp, 0, sizeof(dp));
 82         int mod3 = num[3]+1;
 83         int mod2 = mod3 * (num[2]+1);
 84         int mod1 = mod2 * (num[1]+1);
 85         int limit = num[0]*mod1+num[1]*mod2+num[2]*mod3+num[3];
 86         memset(dp, -1, sizeof(dp));
 87         dp[0][0] = 0;
 88         for(int a=0; a<=num[0]; a++)
 89             for(int b=0; b<=num[1]; b++)
 90                 for(int c=0; c<=num[2]; c++)
 91                     for(int d=0; d<=num[3]; d++)
 92                     {
 93                         int tp = a*mod1 + b*mod2 + c*mod3 + d;
 94                         for(int i=0; i<sz; i++)
 95                         {
 96                             if(dp[i][tp] == -1) continue;
 97                             if(a < num[0]) Max(dp[ch[i][0]][tp+mod1], dp[i][tp]+ed[ch[i][0]]);
 98                             if(b < num[1]) Max(dp[ch[i][1]][tp+mod2], dp[i][tp]+ed[ch[i][1]]);
 99                             if(c < num[2]) Max(dp[ch[i][2]][tp+mod3], dp[i][tp]+ed[ch[i][2]]);
100                             if(d < num[3]) Max(dp[ch[i][3]][tp+1], dp[i][tp]+ed[ch[i][3]]);
101                         }
102                     }
103         int ans = 0;
104         for(int i=0; i<sz; i++)
105             for(int j=0; j<=limit; j++)
106                 Max(ans, dp[i][j]);
107         printf("Case %d: %d
",++cas, ans);
108 
109     }
110     return 0;
111 }

View Code

11. hdu 3247 Resource Archiver

　　给n个资源串和m病毒串，现要把资源串串起来，两串可以重叠，且不含病毒串，求串起来的最短长度。2 <= n <= 10, 1 <= m <= 1000，资源串长不超过10^5，病毒串总长不超过5w。所有串仅由'0''1'组成。

　　很直接的DP方式就是用dp[i][j]表示在Trie树i节点时，匹配情况是j的最短长度。但是6w*(1<<10)MLE。。。

翻了翻网上的题解，大都是说让j表示在第j个单词的末尾。加单词间的最短路。仔细想一想，不对啊，有的资源串的后缀包含了另一个资源，那么另一个资源串不就有多个结尾了吗？

　　还有一种解释是说把带有标记的节点拿出来，最短路+dp，尼玛，最坏情况下每个节点都有标记啊。

　　我看了看他们的代码，发现都一样，那就一个结论了：所有资源串都不是另一个资源串的前缀或后缀。好吧，那就直接用单词末尾的节点来dp吧，先BFS处理任意两个单词末节点的最短路，它的意义是第二个串长与第一个串后缀重合部分长的差，BFS不经过病毒节点就行了。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<queue>
  7 using namespace std;
  8 typedef unsigned long long ull;
  9 const int inf = 0x3f3f3f3f;
 10 const int N = 55555;
 11 const int alp = 2;
 12 const int maxn = 60066;
 13 int ch[maxn][alp], ed[2][maxn], fail[maxn];
 14 int ID[11]; ///第i个串末在自动机中的编号
 15 int root, sz;
 16 int newnode()
 17 {
 18     memset(ch[sz], -1, sizeof(ch[sz]));
 19     ed[0][sz] = ed[1][sz] = 0;
 20     return sz++;
 21 }
 22 void init()
 23 {
 24     sz = 0;
 25     root = newnode();
 26 }
 27 
 28 void Insert(char str[], int id, int tag)
 29 {
 30     int now = root, i;
 31     for(i=0; str[i]; i++)
 32     {
 33         int &tmp = ch[now][str[i]-'0'];
 34         if(tmp == -1) tmp = newnode();
 35         now = tmp;
 36     }
 37     ed[id][now] |= (1<<tag-1);
 38     if(!id) ID[tag] = now;
 39 }
 40 
 41 void build()
 42 {
 43     queue<int> q;
 44     fail[root] = root;
 45     for(int i=0; i<alp; i++)
 46     {
 47         int &tmp = ch[root][i];
 48         if(tmp == -1) tmp = root;
 49         else fail[tmp] = root, q.push(tmp);
 50     }
 51     while(!q.empty())
 52     {
 53         int now = q.front();
 54         q.pop();
 55         ed[0][now] |= ed[0][fail[now]];
 56         ed[1][now] |= ed[1][fail[now]];
 57         for(int i=0; i<alp; i++)
 58         {
 59             int &tmp = ch[now][i];
 60             if(tmp == -1) tmp = ch[fail[now]][i];
 61             else fail[tmp] = ch[fail[now]][i],
 62                  q.push(tmp);
 63         }
 64     }
 65 }
 66 int dis[maxn];
 67 bool vis[maxn];
 68 int w[11][11];
 69 void get_dis(int s, int n)
 70 {
 71     memset(dis, 0x3f, sizeof(dis));
 72     memset(vis, 0, sizeof(vis));
 73     dis[ID[s]] = 0;
 74     vis[ID[s]] = 1;
 75     queue<int>q;
 76     q.push(ID[s]);
 77     while(!q.empty()) {
 78         int u = q.front(); q.pop();
 79         for(int i=0; i<alp; i++)
 80         {
 81             int tmp = ch[u][i];
 82             if(ed[1][tmp]) continue;
 83             if(vis[tmp]) continue;
 84             vis[tmp] = 1;
 85             dis[tmp] = dis[u] + 1;
 86             q.push(tmp);
 87         }
 88     }
 89     for(int i=1; i<=n; i++)
 90         w[s][i] = dis[ID[i]];
 91 }
 92 char str[N];
 93 int len[11];
 94 int dp[1<<10][11];
 95 int main()
 96 {
 97     int i,j,k,m,n;
 98     int p[11];
 99     while(scanf("%d %d",&n,&m) == 2 && n+m)
100     {
101         init();
102         int sum = 0;
103         for(i=1; i<=n; i++)
104             scanf("%s", str), len[i] =  strlen(str), Insert(str, 0, i);
105         for(i=1; i<=m; i++)
106             scanf("%s", str), Insert(str, 1, i);
107         build();
108         ID[0] = root;
109         memset(w, 0x3f, sizeof(w));
110         for(i=0; i<=n; i++) get_dis(i,n);
111         int ans = inf;
112         /***********************************
113          *枚举顺序，简单粗暴
114         for(i=1; i<=n; i++) p[i] = i;
115         do {
116             int ret = 0;
117             for(j=1; j<n; j++)
118                 ret += w[p[j]][p[j+1]];
119             ans = min(ans, ret+len[p[1]]);
120         } while(next_permutation(p+1, p+1+n));
121         ************************************/
122         memset(dp, 0x3f, sizeof(dp));
123         dp[0][0] = 0;
124         for(i=0; i<(1<<n); i++)
125             for(j=0; j<=n; j++)
126         {
127             if(dp[i][j] == inf) continue;
128             for(k=1; k<=n; k++)
129             {
130                 if(w[j][k] == inf) continue;
131                 dp[i|(1<<k-1)][k] = min(dp[i|(1<<k-1)][k], dp[i][j] + w[j][k]);
132             }
133         }
134         for(i=1; i<=n; i++) ans = min(ans, dp[(1<<n)-1][i]);
135         printf("%d
",ans);
136     }
137     return 0;
138 }

View Code

12. zoj 3494 Detect the Viru

　　给n个01病毒串，然后问区间[L,R]内有多少个数的BCD encoding不包含病毒串。一个数的BCD encoding是指每一位数的4bit位连起来的串。

　　n<=100,病毒串长小于20，L<=R<10^200。

　　很好想的数位DP+AC自动机dp[i][j]表示在还有i位且当前在Trie数的j节点的合法数字的个数。

　　注意，如果用字符串读入L和R，要特判L。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<queue>
  7 using namespace std;
  8 typedef unsigned long long ull;
  9 const int inf = 0x3f3f3f3f;
 10 const int mod = 1000000009;
 11 const int N = 222;
 12 const int alp = 10;
 13 const int maxn = 2222;
 14 int ch[maxn][alp], ed[maxn], fail[maxn];
 15 int root, sz;
 16 int newnode()
 17 {
 18     memset(ch[sz], -1, sizeof(ch[sz]));
 19     ed[sz] = 0;
 20     return sz++;
 21 }
 22 void init()
 23 {
 24     sz = 0;
 25     root = newnode();
 26 }
 27 
 28 void Insert(char str[])
 29 {
 30     int now = root, i;
 31     for(i=0; str[i]; i++)
 32     {
 33         int &tmp = ch[now][str[i]-'0'];
 34         if(tmp == -1) tmp = newnode();
 35         now = tmp;
 36     }
 37     ed[now] = 1;
 38 }
 39 
 40 void build()
 41 {
 42     queue<int> q;
 43     fail[root] = root;
 44     for(int i=0; i<alp; i++)
 45     {
 46         int &tmp = ch[root][i];
 47         if(tmp == -1) tmp = root;
 48         else fail[tmp] = root, q.push(tmp);
 49     }
 50     while(!q.empty())
 51     {
 52         int now = q.front();
 53         q.pop();
 54         ed[now] |= ed[fail[now]];
 55         for(int i=0; i<alp; i++)
 56         {
 57             int &tmp = ch[now][i];
 58             if(tmp == -1) tmp = ch[fail[now]][i];
 59             else fail[tmp] = ch[fail[now]][i],
 60                  q.push(tmp);
 61         }
 62     }
 63 }
 64 
 65 int sel[10][4] = {0,0,0,0, 0,0,0,1, 0,0,1,0, 0,0,1,1, 0,1,0,0,
 66                   0,1,0,1, 0,1,1,0, 0,1,1,1, 1,0,0,0, 1,0,0,1};
 67 int query(char str[])
 68 {
 69     int len = strlen(str+1);
 70     int now = root;
 71     for(int i=1; i<=len; i++)
 72     {
 73         int a = str[i] - '0';
 74         for(int j=0; j<4; j++)
 75         {
 76             int tmp = now = ch[now][sel[a][j]];
 77             while(tmp) {
 78                 if(ed[tmp]) return 0;
 79                 tmp = fail[tmp];
 80             }
 81         }
 82     }
 83     return 1;
 84 }
 85 char s[N];
 86 int dp[N][maxn][2];
 87 int DFS(int pos, int id, bool limit, bool pre)
 88 {
 89     if(!pos) return pre;
 90     if(!limit && dp[pos][id][pre] != -1) return dp[pos][id][pre];
 91     int ret = 0;
 92     int end = limit ? s[pos]-'0' : 9;
 93     for(int i=0; i<=end; i++)
 94     {
 95         bool ok = true;
 96         int tmp = id;
 97         if(pre || i)
 98         for(int j=0; j<4; j++)
 99         {
100             tmp = ch[tmp][sel[i][j]];
101             if(ed[tmp]) ok = false;
102         }
103         if(ok) ret =(ret+DFS(pos-1, tmp, limit&&i==end, pre || i))%mod;
104     }
105     if(!limit) dp[pos][id][pre] = ret;
106     return ret;
107 }
108 int main()
109 {
110     int i,j,k,m,n,t;
111     scanf("%d",&t);
112     while(t--)
113     {
114         init();
115         scanf("%d",&n);
116         while(n--) scanf("%s",s+1), Insert(s+1);
117         build();
118         scanf("%s",s+1);
119         m = strlen(s+1);
120         int ans = -query(s);
121         reverse(s+1, s+1+m);
122         for(i=0; i<=m; i++) for(j=0; j<sz; j++) dp[i][j][0]=dp[i][j][1]=-1;
123         ans += DFS(m, 0, 1, 0);
124         scanf("%s",s+1);
125         m = strlen(s+1);
126         reverse(s+1, s+1+m);
127         for(i=0; i<=m; i++) for(j=0; j<sz; j++) dp[i][j][0]=dp[i][j][1]=-1;
128         ans = (DFS(m, 0, 1, 0) - ans)%mod;
129         printf("%d
",(ans+mod)%mod);
130     }
131     return 0;
132 }

View Code

入门题暂时做到这里了( ^_^ )/~~。