【ZOJ】3228 Searching the String

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #define MAXN 100010
  5 #define MAXM 26
  6 #define INF 123456789
  7 using namespace std;
  8 struct Trie {
  9     int fail, pos[2], cnt[2], len, next[MAXM];
 10     void Init() {
 11         len = fail = pos[0] = pos[1] = cnt[0] = cnt[1] = 0;
 12         memset(next, 0, sizeof(next));
 13     }
 14 };
 15 Trie tree[MAXN << 2];
 16 char str[MAXN], s[MAXM];
 17 int size, ans[MAXN], pos[MAXN], vis[MAXN];
 18 inline int GET(char ch) {
 19     return ch - 'a';
 20 }
 21 void Insert(int pos, int x) {
 22     int now, i, t;
 23     for (now = i = 0; s[i]; i++) {
 24         t = GET(s[i]);
 25         if (!tree[now].next[t]) {
 26             tree[++size].Init();
 27             tree[now].next[t] = size;
 28         }
 29         now = tree[now].next[t];
 30     }
 31     tree[now].len = i;
 32     tree[now].pos[x] = pos;
 33     tree[now].cnt[x]++;
 34 }
 35 int Find(int x) {
 36     int now, i, t;
 37     for (now = i = 0; s[i]; i++) {
 38         t = GET(s[i]);
 39         if (!tree[now].next[t])
 40             return 0;
 41         now = tree[now].next[t];
 42     }
 43     return tree[now].pos[x];
 44 }
 45 void BFS() {
 46     int now, i, p;
 47     queue<int> q;
 48     q.push(0);
 49     while (!q.empty()) {
 50         now = q.front();
 51         q.pop();
 52         for (i = 0; i < MAXM; i++) {
 53             if (tree[now].next[i]) {
 54                 p = tree[now].next[i];
 55                 q.push(p);
 56                 if (now)
 57                     tree[p].fail = tree[tree[now].fail].next[i];
 58             } else
 59                 tree[now].next[i] = tree[tree[now].fail].next[i];
 60         }
 61     }
 62 }
 63 void Match() {
 64     int now, t, p, i;
 65     for (now = i = 0; str[i]; i++) {
 66         t = GET(str[i]);
 67         now = tree[now].next[t];
 68         for (p = now; p; p = tree[p].fail) {
 69             if (tree[p].cnt[0])
 70                 ans[tree[p].pos[0]] += tree[p].cnt[0];
 71             if (tree[p].cnt[1] && i - vis[tree[p].pos[1]] >= tree[p].len) {
 72                 vis[tree[p].pos[1]] = i;
 73                 ans[tree[p].pos[1]] += tree[p].cnt[1];
 74             }
 75         }
 76     }
 77 }
 78 int main() {
 79     int n, i, x, ca = 1;
 80     while (~scanf(" %s", str)) {
 81         size = 0;
 82         tree[0].Init();
 83         scanf("%d", &n);
 84         for (i = 1; i <= n; i++) {
 85             ans[i] = 0;
 86             vis[i] = -INF;
 87             scanf("%d %s", &x, s);
 88             pos[i] = Find(x);
 89             if (!pos[i]) {
 90                 pos[i] = i;
 91                 Insert(i, x);
 92             }
 93         }
 94         BFS();
 95         Match();
 96         printf("Case %d\n", ca++);
 97         for (i = 1; i <= n; i++)
 98             printf("%d\n", ans[pos[i]]);
 99         putchar('\n');
100     }
101     return 0;
102 }