Blackops

初心易得，始终难守

0%

ZOJ 3228 Searching the String（AC自动机）

发表于 分类于 ， ，

Searching the String
Time Limit: 7 Seconds Memory Limit: 129872 KB
Little jay really hates to deal with string. But moondy likes it very much, and she’s so mischievous that she often gives jay some dull problems related to string. And one day, moondy gave jay another problem, poor jay finally broke out and cried, “ Who can help me? I’ll bg him! “

So what is the problem this time?

First, moondy gave jay a very long string A. Then she gave him a sequence of very short substrings, and asked him to find how many times each substring appeared in string A. What’s more, she would denote whether or not founded appearances of this substring are allowed to overlap.

At first, jay just read string A from begin to end to search all appearances of each given substring. But he soon felt exhausted and couldn’t go on any more, so he gave up and broke out this time.

I know you’re a good guy and will help with jay even without bg, won’t you?

Input

Input consists of multiple cases( <= 20 ) and terminates with end of file.

For each case, the first line contains string A ( length <= 10^5 ). The second line contains an integer N ( N <= 10^5 ), which denotes the number of queries. The next N lines, each with an integer type and a string a ( length <= 6 ), type = 0 denotes substring a is allowed to overlap and type = 1 denotes not. Note that all input characters are lowercase.

There is a blank line between two consecutive cases.

Output

For each case, output the case number first ( based on 1 , see Samples ).

Then for each query, output an integer in a single line denoting the maximum times you can find the substring under certain rules.

Output an empty line after each case.

Sample Input

ab
2
0 ab
1 ab

abababac
2
0 aba
1 aba

abcdefghijklmnopqrstuvwxyz
3
0 abc
1 def
1 jmn
Sample Output

Case 1
1
1

Case 2
3
2

Case 3
1
1
0

Hint

In Case 2,you can find the first substring starting in position (indexed from 0) 0,2,4, since they’re allowed to overlap. The second substring starts in position 0 and 4, since they’re not allowed to overlap.

For C++ users, kindly use scanf to avoid TLE for huge inputs.

题目链接：ZOJ 3228
就是给定一系列询问，求询问所给的子串在主串中出现的次数，由于fail指针的特性，可以把子串加入字典树后建立AC自动机，然后拿主串在上面跑一遍AC自动机，然后把字典树上的节点被遍历次数记录下来，就是对应可覆盖的答案了。
不可覆盖的话就记录一下上一次跑过的那个点在主串中的下标，
如果$当前节点对应下标 - 上一次下标 \ge 这个节点对应字符串长度$，就说明不可覆盖的出现了$1$次。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 6e5 + 10;
struct Trie
{
    int nxt[26], fail;
    void init()
    {
        for (int i = 0; i < 26; ++i)
            nxt[i] = -1;
        fail = 0;
    }
} L[N];
int sz;
int cnt[N][2], End[N], Len[N], last[N];
char s[N], t[10];
int ops[N];

void init()
{
    CLR(cnt, 0);
    CLR(last, -1);
}
namespace ac
{
    void init()
    {
        sz = 0;
        L[sz++].init();
    }
    void ins(char s[], int len, int id)
    {
        int u = 0;
        for (int i = 0; i < len; ++i)
        {
            int v = s[i] - 'a';
            if (L[u].nxt[v] == -1)
            {
                L[sz].init();
                L[u].nxt[v] = sz++;
            }
            u = L[u].nxt[v];
            Len[u] = i + 1;
        }
        End[id] = u;
    }
    void build()
    {
        L[0].fail = 0;
        queue<int>Q;
        for (int i = 0; i < 26; ++i)
        {
            int v = L[0].nxt[i];
            if (~v)
            {
                L[v].fail = 0;
                Q.push(v);
            }
            else
                L[0].nxt[i] = 0;
        }
        while (!Q.empty())
        {
            int u = Q.front();
            Q.pop();
            int uf = L[u].fail;
            for (int i = 0; i < 26; ++i)
            {
                int v = L[u].nxt[i];
                if (~v)
                {
                    L[v].fail = L[uf].nxt[i];
                    Q.push(v);
                }
                else
                    L[u].nxt[i] = L[uf].nxt[i];
            }
        }
    }
    void query(char s[], int len)
    {
        int u = 0;
        for (int i = 0; i < len; ++i)
        {
            int v = s[i] - 'a';
            u = L[u].nxt[v];
            int tu = u;
            while (tu)
            {
                ++cnt[tu][0];
                if (i - last[tu] >= Len[tu])
                {
                    ++cnt[tu][1];
                    last[tu] = i;
                }
                tu = L[tu].fail;
            }
        }
    }
}
int main(void)
{
    int T = 0, i, n;
    while (~scanf("%s", s))
    {
        ac::init();
        init();
        scanf("%d", &n);
        for (i = 1; i <= n; ++i)
        {
            scanf("%d%s", &ops[i], t);
            ac::ins(t, strlen(t), i);
        }
        ac::build();
        ac::query(s, strlen(s));
        printf("Case %d\n", ++T);
        for (i = 1; i <= n; ++i)
            printf("%d\n", cnt[End[i]][ops[i]]);
        puts("");
    }
    return 0;
}