Blackops

初心易得，始终难守

0%

HDU 6208 The Dominator of Strings（AC自动机）

发表于 更新于 分类于 ， ，

The Dominator of Strings

Time Limit: 3000/3000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 2830 Accepted Submission(s): 1010

Problem Description
Here you have a set of strings. A dominator is a string of the set dominating all strings else. The string S is dominated by T if S is a substring of T.

Input
The input contains several test cases and the first line provides the total number of cases.
For each test case, the first line contains an integer N indicating the size of the set.
Each of the following N lines describes a string of the set in lowercase.
The total length of strings in each case has the limit of 100000.
The limit is 30MB for the input file.

Output
For each test case, output a dominator if exist, or No if not.

Sample Input
3
10
you
better
worse
richer
poorer
sickness
health
death
faithfulness
youbemyweddedwifebetterworsericherpoorersicknesshealthtilldeathdouspartandpledgeyoumyfaithfulness
5
abc
cde
abcde
abcde
bcde
3
aaaaa
aaaab
aaaac

Sample Output
youbemyweddedwifebetterworsericherpoorersicknesshealthtilldeathdouspartandpledgeyoumyfaithfulness
abcde
No

Source
2017 ACM/ICPC Asia Regional Qingdao Online

题目链接：HDU 6208
检测你的AC自动机是否正确以及优化是否优秀的模板题，每一次把路径上的节点累加个数置为-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
145
146
147
148
149
150
151
152
#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 = 100010;
struct Trie
{
    int nxt[26];
    int cnt, fail;
    void init()
    {
        for (int i = 0; i < 26; ++i)
            nxt[i] = -1;
        cnt = fail = 0;
    }
} L[N];
char s[N];
int st[N], Len[N];
int tot;

namespace AC
{
    void init()
    {
        tot = 0;
        L[tot++].init();
    }
    void insert(char s[], int len)
    {
        int u = 0;
        for (int i = 0; i < len; ++i)
        {
            int v = s[i] - 'a';
            if (L[u].nxt[v] == -1)
            {
                L[tot].init();
                L[u].nxt[v] = tot++;
            }
            u = L[u].nxt[v];
        }
        ++L[u].cnt;
    }
    void build()
    {
        L[0].fail = 0;
        queue<int>Q;
        for (int i = 0; i < 26; ++i)
        {
            if (L[0].nxt[i] == -1)
                L[0].nxt[i] = 0;
            else
            {
                L[L[0].nxt[i]].fail = 0;
                Q.push(L[0].nxt[i]);
            }
        }
        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 == -1)
                    L[u].nxt[i] = L[uf].nxt[i];
                else
                {
                    L[v].fail = L[uf].nxt[i];
                    Q.push(v);
                }
            }
        }
    }
    int query(char s[], int len)
    {
        int ret = 0;
        int u = 0;
        for (int i = 0; i < len; ++i)
        {
            int v = s[i] - 'a';
            u = L[u].nxt[v];
            while (u && L[u].nxt[v] == -1)
                u = L[u].fail;
            int t = u;
            while (t && L[t].cnt != -1)
            {
                ret += L[t].cnt;
                L[t].cnt = -1;
                t = L[t].fail;
            }
        }
        return ret;
    }
}
int main(void)
{
    int T, n, i;
    scanf("%d", &T);
    while (T--)
    {
        AC::init();
        scanf("%d", &n);
        int sum = 0;
        int Maxlen = 0;
        int ID = 0;
        for (i = 0; i < n; ++i)
        {
            scanf("%s", s + sum);
            Len[i] = strlen(s + sum);
            AC::insert(s + sum, Len[i]);
            st[i] = sum;
            sum += Len[i];
            if (Len[i] > Maxlen)
            {
                ID = i;
                Maxlen = Len[i];
            }
        }
        AC::build();
        if (AC::query(s + st[ID], Len[ID]) == n)
        {
            int ed = st[ID] + Len[ID];
            for (i = st[ID]; i < ed; ++i)
                printf("%c", s[i]);
            puts("");
        }
        else
            puts("No");
    }
    return 0;
}