POJ 2778:DNA Sequence(AC自动机构造矩阵)

http://poj.org/problem?id=2778

题意:有m个病毒DNA,问构造一个长度为n的不带病毒DNA的字符串可以有多少种。

思路:看到这题有点懵,想了挺久题解的思路。

使用AC自动机判断总共有哪些状态,和哪些状态是不可取的。

然后构造出矩阵mat,mat[i][j]代表从状态i走到状态j走一步可以有多少种走法,然后走n步就是mat[i][j]^n(就像你走第一步可以有2种走法,走第二步可以有2^2种走法,走第三步可以有2^3种走法一样的道理(一开始还想不懂))。

在AC自动机判断状态不可取的时候,不但是插入的串末尾不可取,而且如果fail指针指向的状态是不可取的,那么当前的状态也是不可取的!因为fail指针指向的是当前匹配了的串的最长后缀,那么当前匹配了的串必定包含了fail指针指向的串(病毒串)。

还参考了很多数据==。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <queue>
  4 using namespace std;
  5 #define N 105
  6 #define TOL 4
  7 #define MOD 100000
  8 typedef long long LL;
  9 
 10 int sz;
 11 
 12 typedef struct Node {
 13     Node *next[TOL];
 14     Node *fail; int flag, id;
 15     Node () {
 16         for(int i = 0; i < TOL; i++) next[i] = NULL;
 17         fail = NULL; flag = 0; id = sz++;
 18     }
 19 } node;
 20 
 21 class Matrix {
 22 
 23     public:
 24 
 25         LL mat[N][N];
 26 
 27         void init() { memset(mat, 0, sizeof(mat)); }
 28 
 29         void identity() { memset(mat, 0, sizeof(mat)); for(int i = 0; i < sz; i++) mat[i][i] = 1; }
 30 
 31         static void print(Matrix now) {
 32             printf("sz : %d
", sz);
 33             for(int i = 0; i < sz; i++) {
 34                 for(int j = 0; j < sz; j++) {
 35                     printf("%d ", now.mat[i][j]);
 36                 }
 37                 puts("");
 38             }
 39         }
 40 
 41         friend Matrix operator * (const Matrix &a, const Matrix &b) {
 42             Matrix c; c.init();
 43             for(int i = 0; i < sz; i++) {
 44                 for(int k = 0; k < sz; k++) {
 45                     for(int j = 0; j < sz; j++) {
 46                         c.mat[i][k] = c.mat[i][k] + a.mat[i][j] * b.mat[j][k];
 47                     }
 48                     c.mat[i][k] %= MOD; // 如果放在里面会TLE
 49                 }
 50             }
 51             return c;
 52         }
 53 
 54         friend Matrix operator ^ (Matrix a, int k) {
 55             Matrix b; b.identity();
 56             while(k) {
 57                 if(k & 1) b = b * a;
 58                 a = a * a;
 59                 k >>= 1;
 60             }
 61             return b;
 62         }
 63 
 64         void solve(Matrix now, int n) {
 65             now = now ^ n;
 66             int sum = 0;
 67             for(int i = 0; i < sz; i++) { sum = (sum + now.mat[0][i]); if(sum >= MOD) sum -= MOD; }
 68             printf("%d
", sum % MOD);
 69         }
 70 };
 71 
 72 class AC_DFA {
 73 
 74     private:
 75 
 76         node* root;
 77         vector<node*> dic;
 78 
 79     public:
 80 
 81         AC_DFA() {
 82             dic.clear();
 83             root = new node();
 84             sz = 1; dic.push_back(root);
 85         }
 86 
 87         ~AC_DFA() {
 88             for(int i = 0; i < sz; i++) delete dic[i];
 89         }
 90 
 91         int get(char c) {
 92             if(c == 'A') return 0;
 93             if(c == 'C') return 1;
 94             if(c == 'G') return 2;
 95             return 3;
 96         }
 97 
 98         void insert(char *s) {
 99             node* now = root;
100             int len = strlen(s);
101             for(int i = 0; i < len; i++) {
102                 int c = get(s[i]);
103                 if(now->next[c] == NULL) now->next[c] = new node(), dic.push_back(now->next[c]);
104                 now = now->next[c];
105             }
106             now->flag = 1;
107         }
108 
109         void build() {
110             queue<node*> que;
111             root->fail = NULL;
112             que.push(root);
113             while(!que.empty()) {
114                 node* now = que.front(); que.pop();
115                 for(int i = 0; i < TOL; i++) {
116                     if(now->next[i]) {
117                         node* p = now->fail;
118                         while(p && p->next[i] == NULL) p = p->fail;
119                         // 如果指向的fail是病毒,那么now->next[i]也是带病毒的,因为指向的fail是其最大后缀
120                         if(p) now->next[i]->fail = p->next[i], now->next[i]->flag |= p->next[i]->flag;
121                         else now->next[i]->fail = root;
122                         que.push(now->next[i]);
123                     } else {
124                         if(now == root) now->next[i] = root;
125                         else now->next[i] = now->fail->next[i];
126                     }
127                 }
128             }
129         }
130 
131         Matrix buildMatrix() {
132             Matrix a; a.init();
133             for(int i = 0; i < dic.size(); i++) {
134                 for(int j = 0; j < TOL; j++) {
135                     if(dic[i]->next[j]->flag == 0) {
136                         int tmp = dic[i]->next[j]->id;
137                         a.mat[i][tmp]++;
138                     }
139                 }
140             }
141             return a;
142         }
143 };
144 
145 int main() {
146     int m, n;
147     scanf("%d%d", &m, &n);
148     char s[N];
149     AC_DFA ac;
150     for(int i = 0; i < m; i++)
151         scanf("%s", s), ac.insert(s);
152     ac.build();
153     Matrix now = ac.buildMatrix();
154     now.solve(now, n);
155     return 0;
156 }
157 
158 /*
159 4 3
160 AT
161 AC
162 AG
163 AA
164 10 100
165 AGAGAGT
166 CGTATTG
167 AAAATTTCGC
168 GCGTA
169 TCGA
170 AATTGGA
171 TAGATAGC
172 AGCGTATT
173 TTCGA
174 TACGTATTG
175 3 10
176 AT
177 GATC
178 TGAC
179 48233
180 */
原文地址:https://www.cnblogs.com/fightfordream/p/6599600.html