lightoj1427

maksyuki 发表于 oj 分类，标签: 字符串-AC自动机

27 8月 2015

1427 - Substring Frequency (II)

InputA string is a finite sequence of symbols that are chosen from an alphabet. In this problem you are given a string T and n queries each with a string P_i, where the strings contain lower case English alphabets only. You have to find the number of times P_i occurs as a substring of T.

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 500). The next line contains the string T (1 ≤ |T| ≤ 10⁶). Each of the next n lines contains a string P_i (1 ≤ |P_i| ≤ 500).

Output

For each case, print the case number in a single line first. Then for each string P_i, report the number of times it occurs as a substring of T in a single line.

Sample Input

Output for Sample Input

25ababacbabcababa

abc

lightoj

light

lit

Case 1:2314

Case 2:

Notes

Dataset is huge, use faster I/O methods.
If S is a string then |S| denotes the length of S.

题目类型：AC自动机

算法分析：将子串插入到Trie树中，然后使用cnt数组统计在文本串T中，相应子串出现的个数即可，注意子串可能出现重复的情况！！！由于n比较小，所以可以使用O(n^2)的枚举将标号后面重复的相应子串的个数求解得到

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 1e9 + 7;
const int maxn = 26;
const int nodemaxn = 250000 + 66;

char ss[1000000+maxn];
int cnt[500+maxn];
char val[500+maxn][500+maxn];

struct ACNode
{
    int next[nodemaxn][maxn], pre[nodemaxn], last[nodemaxn], id[nodemaxn];
    int root, len;

    void Init ()
    {
        len = 0;
        root = newnode ();
    }

    int newnode ()
    {
        for (int i = 0; i < maxn; i++)
            next[len][i] = -1;
        last[len] = id[len] = 0;
        len++;

        return len - 1;
    }

    void Insert (char *s, int ff)
    {
        int p = root;
        for(int i = 0; s[i]; i++)
        {
            if(next[p][s[i]-'a'] == -1)
                next[p][s[i]-'a'] = newnode ();

            p = next[p][s[i]-'a'];
        }
        last[p]++;
        id[p] = ff;
    }

    void Build ()
    {
        queue <int> qu;
        pre[root] = root;
        for(int i = 0; i < maxn; i++)
        {
            if(next[root][i] == -1)
                next[root][i] = root;

            else
            {
                pre[next[root][i]] = root;
                qu.push (next[root][i]);
            }
        }

        while (!qu.empty ())
        {
            int p = qu.front(); qu.pop ();
            for (int i = 0; i < maxn; i++)
            {
                if (next[p][i] == -1)
                    next[p][i] = next[pre[p]][i];

                else
                {
                    pre[next[p][i]] =  next[pre[p]][i];
                    qu.push (next[p][i]);
                }
            }
        }
    }

    void Query (char *s)
    {
        int p = root;
        for (int i = 0; s[i]; i++)
        {

            p = next[p][s[i]-'a'];//一步到位，重要!!! 当存在时走到下一层，否则回溯!!!
            int temp = p;

            while (temp != root)
            {
                if (last[temp])
                {
                    cnt[id[temp]]++;
                }
                temp = pre[temp];
            }
        }
    }
};

ACNode ac;

int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int n, t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        printf ("Case %d:\n", flag++);
        scanf ("%d", &n);
        scanf ("%s", ss);

        ac.Init ();
        memset (cnt, 0, sizeof (cnt));

        for (int i = 1; i <= n; i++)
        {
            scanf ("%s", val[i]);

            int j;
            for (j = 1; j < i; j++)
                if (!strcmp (val[j], val[i]))
                    break;

            if (j >= i)
                ac.Insert (val[i], i);
        }

        ac.Build ();
        ac.Query (ss);

        for (int i = 1; i <= n; i++)
        {
            int j;
            for (j = 1; j < i; j++)
                if (!strcmp (val[j], val[i]))
                    break;

            if (j < i)
                printf ("%d\n", cnt[j]);

            else
                printf ("%d\n", cnt[i]);
        }
    }

return 0;
}

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

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 1e9 + 7;

const int maxn = 26;

const int nodemaxn = 250000 + 66;

char ss[1000000+maxn];

int cnt[500+maxn];

char val[500+maxn][500+maxn];

struct ACNode

{

int next[nodemaxn][maxn], pre[nodemaxn], last[nodemaxn], id[nodemaxn];

int root, len;

void Init ()

{

len = 0;

root = newnode ();

}

int newnode ()

{

for (int i = 0; i < maxn; i++)

next[len][i] = -1;

last[len] = id[len] = 0;

len++;

return len - 1;

}

void Insert (char *s, int ff)

{

int p = root;

for(int i = 0; s[i]; i++)

{

if(next[p][s[i]-'a'] == -1)

next[p][s[i]-'a'] = newnode ();

p = next[p][s[i]-'a'];

}

last[p]++;

id[p] = ff;

}

void Build ()

{

queue <int> qu;

pre[root] = root;

for(int i = 0; i < maxn; i++)

{

if(next[root][i] == -1)

next[root][i] = root;

else

{

pre[next[root][i]] = root;

qu.push (next[root][i]);

}

while (!qu.empty ())

{

int p = qu.front(); qu.pop ();

for (int i = 0; i < maxn; i++)

{

if (next[p][i] == -1)

next[p][i] = next[pre[p]][i];

else

{

pre[next[p][i]] = next[pre[p]][i];

qu.push (next[p][i]);

}

void Query (char *s)

{

int p = root;

for (int i = 0; s[i]; i++)

{

p = next[p][s[i]-'a'];//一步到位，重要!!! 当存在时走到下一层，否则回溯!!!

int temp = p;

while (temp != root)

{

if (last[temp])

{

cnt[id[temp]]++;

}

temp = pre[temp];

}

};

ACNode ac;

int main()

{

// freopen ("aaa.txt", "r", stdin);

int n, t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d:\n", flag++);

scanf ("%d", &n);

scanf ("%s", ss);

ac.Init ();

memset (cnt, 0, sizeof (cnt));

for (int i = 1; i <= n; i++)

{

scanf ("%s", val[i]);

int j;

for (j = 1; j < i; j++)

if (!strcmp (val[j], val[i]))

break;

if (j >= i)

ac.Insert (val[i], i);

}

ac.Build ();

ac.Query (ss);

for (int i = 1; i <= n; i++)

{

int j;

for (j = 1; j < i; j++)

if (!strcmp (val[j], val[i]))

break;

if (j < i)

printf ("%d\n", cnt[j]);

else

printf ("%d\n", cnt[i]);

}

return 0;

}

lightoj1369

xdu1028

超客的水墨烟雨

lightoj1427

Output

Sample Input

Output for Sample Input

Notes

分类目录

标签云

书签

近期评论

2025年4月
一	二	三	四	五	六	日
« 6月
	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