【HDU】3341 Lost's revenge

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #define MAXN 15000
  5 #define MAXM 510
  6 using namespace std;
  7 int size, K[5], dp[MAXN][MAXM];
  8 bool vis[MAXN];
  9 char str[MAXM];
 10 struct Trie {
 11     int cnt, fail, next[4];
 12     void Init() {
 13         cnt = fail = 0;
 14         memset(next, 0, sizeof(next));
 15     }
 16 };
 17 Trie tree[MAXM];
 18 inline int MAX(int x, int y) {
 19     return x > y ? x : y;
 20 }
 21 inline int GET(char ch) {
 22     if (ch == 'A')
 23         return 0;
 24     if (ch == 'C')
 25         return 1;
 26     if (ch == 'G')
 27         return 2;
 28     return 3;
 29 }
 30 void Insert(char *s) {
 31     int now, t;
 32     for (now = 0; *s; s++) {
 33         t = GET(*s);
 34         if (!tree[now].next[t]) {
 35             tree[++size].Init();
 36             tree[now].next[t] = size;
 37         }
 38         now = tree[now].next[t];
 39     }
 40     tree[now].cnt++;
 41 }
 42 void BFS() {
 43     int now, i, p;
 44     queue<int> q;
 45     q.push(0);
 46     while (!q.empty()) {
 47         now = q.front();
 48         q.pop();
 49         for (i = 0; i < 4; i++) {
 50             if (tree[now].next[i]) {
 51                 p = tree[now].next[i];
 52                 q.push(p);
 53                 if (now) {
 54                     tree[p].fail = tree[tree[now].fail].next[i];
 55                     tree[p].cnt += tree[tree[p].fail].cnt;
 56                 }
 57             } else
 58                 tree[now].next[i] = tree[tree[now].fail].next[i];
 59         }
 60     }
 61 }
 62 void DoIt() {
 63     queue<int> q;
 64     int head, temp;
 65     int i, j, k, ans, cnt[4];
 66     memset(dp, -1, sizeof(dp));
 67     memset(vis, false, sizeof(vis));
 68     memset(cnt, 0, sizeof(cnt));
 69     for (i = 0; str[i]; i++)
 70         cnt[GET(str[i])]++;
 71     for (i = 0; i < 5; i++) {
 72         if (i)
 73             K[i] = K[i - 1] * (cnt[i - 1] + 1);
 74         else
 75             K[i] = 1;
 76     }
 77     ans = 0;
 78     dp[0][0] = 0;
 79     q.push(0);
 80     vis[0] = true;
 81     while (!q.empty()) {
 82         head = q.front();
 83         q.pop();
 84         for (i = 0; i <= size; i++) {
 85             if (dp[head][i] < 0)
 86                 continue;
 87             for (j = 0; j < 4; j++) {
 88                 k = head % K[j + 1] / K[j];
 89                 if (k >= cnt[j])
 90                     continue;
 91                 temp = head + K[j];
 92                 k = tree[i].next[j];
 93                 if (dp[head][i] + tree[k].cnt > dp[temp][k]) {
 94                     dp[temp][k] = dp[head][i] + tree[k].cnt;
 95                     ans = MAX(ans, dp[temp][k]);
 96                     if (!vis[temp]) {
 97                         vis[temp] = true;
 98                         q.push(temp);
 99                     }
100                 }
101             }
102         }
103     }
104     printf("%d\n", ans);
105 }
106 int main() {
107     int n, ca = 1;
108     while (scanf("%d", &n), n) {
109         tree[0].Init();
110         for (size = 0; n--;) {
111             scanf(" %s", str);
112             Insert(str);
113         }
114         scanf(" %s", str);
115         BFS();
116         printf("Case %d: ", ca++);
117         DoIt();
118     }
119     return 0;
120 }