hdu2222

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

15 9月 2015

Keywords Search

Problem Description

In the modern time, Search engine came into the life of everybody like Google, Baidu, etc.
Wiskey also wants to bring this feature to his image retrieval system.
Every image have a long description, when users type some keywords to find the image, the system will match the keywords with description of image and show the image which the most keywords be matched.
To simplify the problem, giving you a description of image, and some keywords, you should tell me how many keywords will be match.

Input

First line will contain one integer means how many cases will follow by.
Each case will contain two integers N means the number of keywords and N keywords follow. (N <= 10000)
Each keyword will only contains characters 'a'-'z', and the length will be not longer than 50.
The last line is the description, and the length will be not longer than 1000000.

Output

Print how many keywords are contained in the description.

Sample Input

she

say

shr

her

yasherhs

Sample Output

Author

Wiskey

题目类型：AC自动机

算法分析：直接将按照单词建立一个AC自动机，然后如果找到一个匹配的模式串，则不断寻找这个模式串的后缀，看能不能又找到一个匹配的模式串，防止漏解。注意使用G++会MLE！！！

#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;

char ss[1000000+maxn];

struct Node
{
    Node *next[maxn];
    Node *pre;
    int last;
    Node ()
    {
        memset (next, 0, sizeof (next));
        pre = 0, last = 0;
    }
};

Node *root;

void Init ()
{
    root = new Node;
}

void Insert (char *s)
{
    if (!s[0]) return ;

    Node *p = root;
    for (int i = 0; s[i]; i++)
    {
        if (!p -> next[s[i]-'a'])
            p -> next[s[i]-'a'] = new Node;

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

void Build ()
{
    queue <Node*> qu;
    Node *p = root;
    for (int i = 0; i < maxn; i++)
        if (p -> next[i])
        {
            Node *pp = p -> next[i];
            pp -> pre = root;
            qu.push (pp);
        }

    while (!qu.empty ())
    {
        Node *temp = qu.front (); qu.pop ();
        for (int i = 0; i < maxn; i++)
        {
            Node *pp = temp -> next[i];
            if (pp)
            {
                Node *par = temp -> pre;
                do
                {
                    if (par -> next[i])
                    {
                        pp -> pre = par -> next[i];
                        break;
                    }

                    else
                        par = par -> pre;
                } while (par);

                if (!par)
                    pp -> pre = root;

                qu.push (pp);
            }
        }
    }
}

int Query (char *s)
{
    if (!s[0]) return 0;

    Node *p = root;
    int cnt = 0;
    for (int i = 0; s[i]; i++)
    {
        while (p != root && !p -> next[s[i]-'a'])
            p = p -> pre;

        p = p -> next[s[i]-'a'];
        if (!p)
            p = root;

        Node *pp = p;
        while (pp != root && pp -> last != -1)
        {
            cnt += pp -> last;
            pp -> last = -1;
            pp = pp -> pre;
        }
    }
return cnt;
}

void DelTree (Node *s)
{
    if (!s) return ;

    for (int i = 0; i < maxn; i++)
    {
        if (s -> next[i])
            DelTree (s -> next[i]);
    }
    delete s;
}

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

    int t;
    scanf ("%d", &t);
    while (t--)
    {
        int n;
        scanf ("%d",&n);
        Init ();

        for (int i = 1; i <= n; i++)
        {
            scanf ("%s", ss);
            Insert (ss);
        }

        gets (ss);
        gets (ss);

        Build ();

        printf ("%d\n", Query (ss));
        DelTree (root);
    }

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;

char ss[1000000+maxn];

struct Node

{

Node *next[maxn];

Node *pre;

int last;

Node ()

{

memset (next, 0, sizeof (next));

pre = 0, last = 0;

}

};

Node *root;

void Init ()

{

root = new Node;

}

void Insert (char *s)

{

if (!s[0]) return ;

Node *p = root;

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

{

if (!p -> next[s[i]-'a'])

p -> next[s[i]-'a'] = new Node;

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

}

p -> last++;

}

void Build ()

{

queue <Node*> qu;

Node *p = root;

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

if (p -> next[i])

{

Node *pp = p -> next[i];

pp -> pre = root;

qu.push (pp);

}

while (!qu.empty ())

{

Node *temp = qu.front (); qu.pop ();

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

{

Node *pp = temp -> next[i];

if (pp)

{

Node *par = temp -> pre;

{

if (par -> next[i])

{

pp -> pre = par -> next[i];

break;

}

else

par = par -> pre;

} while (par);

if (!par)

pp -> pre = root;

qu.push (pp);

}

int Query (char *s)

{

if (!s[0]) return 0;

Node *p = root;

int cnt = 0;

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

{

while (p != root && !p -> next[s[i]-'a'])

p = p -> pre;

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

if (!p)

p = root;

Node *pp = p;

while (pp != root && pp -> last != -1)

{

cnt += pp -> last;

pp -> last = -1;

pp = pp -> pre;

}

return cnt;

}

void DelTree (Node *s)

{

if (!s) return ;

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

{

if (s -> next[i])

DelTree (s -> next[i]);

}

delete s;

}

int main()

{

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

int t;

scanf ("%d", &t);

while (t--)

{

int n;

scanf ("%d",&n);

Init ();

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

{

scanf ("%s", ss);

Insert (ss);

}

gets (ss);

Build ();

printf ("%d\n", Query (ss));

DelTree (root);

}

return 0;

}

hdu2191

hdu2521

超客的水墨烟雨

hdu2222

Keywords Search

分类目录

标签云

书签

近期评论

2024年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