hdu2896

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

15 9月 2015

病毒侵袭

Problem Description

当太阳的光辉逐渐被月亮遮蔽，世界失去了光明，大地迎来最黑暗的时刻。。。。在这样的时刻，人们却异常兴奋——我们能在有生之年看到500年一遇的世界奇观，那是多么幸福的事儿啊~~
但网路上总有那么些网站，开始借着民众的好奇心，打着介绍日食的旗号，大肆传播病毒。小t不幸成为受害者之一。小t如此生气，他决定要把世界上所有带病毒的网站都找出来。当然，谁都知道这是不可能的。小t却执意要完成这不能的任务，他说：“子子孙孙无穷匮也！”（愚公后继有人了）。
万事开头难，小t收集了好多病毒的特征码，又收集了一批诡异网站的源码，他想知道这些网站中哪些是有病毒的，又是带了怎样的病毒呢？顺便还想知道他到底收集了多少带病毒的网站。这时候他却不知道何从下手了。所以想请大家帮帮忙。小t又是个急性子哦，所以解决问题越快越好哦~~

Input

第一行，一个整数N（1<=N<=500），表示病毒特征码的个数。
接下来N行，每行表示一个病毒特征码，特征码字符串长度在20—200之间。
每个病毒都有一个编号，依此为1—N。
不同编号的病毒特征码不会相同。
在这之后一行，有一个整数M（1<=M<=1000），表示网站数。
接下来M行，每行表示一个网站源码，源码字符串长度在7000—10000之间。
每个网站都有一个编号，依此为1—M。
以上字符串中字符都是ASCII码可见字符（不包括回车）。

Output

依次按如下格式输出按网站编号从小到大输出，带病毒的网站编号和包含病毒编号，每行一个含毒网站信息。
web 网站编号: 病毒编号病毒编号 …
冒号后有一个空格，病毒编号按从小到大排列，两个病毒编号之间用一个空格隔开，如果一个网站包含病毒，病毒数不会超过3个。
最后一行输出统计信息，如下格式
total: 带病毒网站数
冒号后有一个空格。

Sample Input

aaa

bbb

ccc

aaabbbccc

bbaacc

Sample Output

web 1: 1 2 3

total: 1

Source

2009 Multi-University Training Contest 10 - Host by NIT

题目类型：AC自动机

算法分析：将病毒的识别码插入到Trie树中，然后对于标号从小到大的网站，依次尝试匹配病毒的识别码，将匹配的找出来，然后按照从小到的顺序输出。注意虽然每次查找都会向前查当前串的后缀，但是不会出现查找重复的情况(易证)

#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 = 127 + 6;


char ss[10000+maxn];
int aa[6], aalen;


struct ACNode
{
    int next[100010][maxn], pre[100010], last[100010], id[100010];
    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]-32] == -1)
                next[p][s[i]-32] = newnode ();

            p = next[p][s[i]-32];
        }
        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]-32];//一步到位，重要!!! 当存在时走到下一层，否则回溯!!!
            int temp = p;
            while (temp != root)
            {
                if (last[temp])
                {
//                    last[temp] = 0;
                    aa[aalen++] = id[temp];
                }
                temp = pre[temp];
            }
        }
    }
};


ACNode ac;

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

    int n;
    scanf ("%d", &n);

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

    ac.Build ();

    int m, cnt = 0;
    scanf ("%d", &m);
    gets (ss);

    for (int i = 1; i <= m; i++)
    {
        gets (ss);
        aalen = 0;
        ac.Query (ss);

        if (aalen)
        {
            sort (aa, aa + aalen);
            printf ("web %d:", i);
            for (int i = 0; i < aalen; i++)
                printf (" %d", aa[i]);
            puts ("");
            cnt++;
        }
    }

    printf ("total: %d\n", cnt);

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

#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 = 127 + 6;

char ss[10000+maxn];

int aa[6], aalen;

struct ACNode

{

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

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]-32] == -1)

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

p = next[p][s[i]-32];

}

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]-32];//一步到位，重要!!! 当存在时走到下一层，否则回溯!!!

int temp = p;

while (temp != root)

{

if (last[temp])

{

// last[temp] = 0;

aa[aalen++] = id[temp];

}

temp = pre[temp];

}

};

ACNode ac;

int main()

{

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

int n;

scanf ("%d", &n);

ac.Init ();

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

{

scanf ("%s", ss);

ac.Insert (ss, i);

}

ac.Build ();

int m, cnt = 0;

scanf ("%d", &m);

gets (ss);

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

{

gets (ss);

aalen = 0;

ac.Query (ss);

if (aalen)

{

sort (aa, aa + aalen);

printf ("web %d:", i);

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

printf (" %d", aa[i]);

puts ("");

cnt++;

}

printf ("total: %d\n", cnt);

return 0;

}

hdu2888

hdu2955

超客的水墨烟雨

hdu2896

病毒侵袭

分类目录

标签云

书签

近期评论

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