HDU 5853 Jong Hyok and String【后缀自动机】

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=5853

题意:

给定$n$个字符串,$m$个询问,对于每个询问中的字符串,求$n$个串中有多少个和其$right$集相同的子串。
数据范围:$1 \le n \le 100000, 1 \le m \le 500000$

分析:

对于多个字符串建立后缀自动机,对于询问串放在后缀自动机上跑一遍。
以字符串$Q$最后一个字符为最后一个字符的后缀长度在$(st[st[now].link].len, st[now].len]$之间,就是说长度在这个范围内的所有子串都满足题意,个数也可以计算出来了。


人生第一道SAM ^-^
推荐的资料们
https://saisumit.wordpress.com/2016/01/26/suffix-automaton/
http://blog.sina.com.cn/s/blog_70811e1a01014dkz.html

代码:

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
/*************************************************************************
> File Name: 5853.cpp
> Author: jiangyuzhu
> Mail: 834138558@qq.com
> Created Time: 2016/10/9 16:46:37
************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
struct state {
int len, link;
int nex[26];
};
const int maxn = 123456, maxs = 100000;
state st[maxs * 2];
int sz, last;
void sa_init()
{
sz = last = 0;
st[0].len = 0;
memset(st[0].nex, -1, sizeof(st[0].nex));
st[0].link = -1;
++sz;
}
//root is 0
void sa_extend (int c)
{
int cur = sz++;
memset(st[cur].nex, -1, sizeof(st[cur].nex));
st[cur].len = st[last].len + 1;
int p;
for (p = last; p != -1 && st[p].nex[c] == -1; p = st[p].link)
st[p].nex[c] = cur;
if (p == -1)
st[cur].link = 0;
else {
int q = st[p].nex[c];
if (st[p].len + 1 == st[q].len)
st[cur].link = q;
else {
int clone = sz++;
st[clone].len = st[p].len + 1;
memcpy(st[clone].nex, st[q].nex, sizeof(st[q].nex));
st[clone].link = st[q].link;
for (; p!=-1 && st[p].nex[c] == q; p = st[p].link)
st[p].nex[c] = clone;
st[q].link = st[cur].link = clone;
}
}
last = cur;
}
void build(char* s)
{
last = 0;
for(int i = 0; s[i]; ++i){
sa_extend(s[i] - 'a');
}
}
char s[maxn];
int main (void)
{
int T;scanf("%d", &T);
for(int tt = 1; tt <= T; ++tt){
sa_init();
int n, m;scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i){
scanf("%s", s);
build(s);
}
printf("Case #%d:\n", tt);
for(int i = 0; i < m; ++i){
scanf("%s", s);
int now = 0;
bool flag = false;
for(int j = 0; s[j]; ++j){
now = st[now].nex[s[j] - 'a'];
if(now == -1){
flag = true;
puts("0");
break;
}
}
if(!flag) printf("%d\n", st[now].len - st[st[now].link].len);
}
}
return 0;
}
文章目录
  1. 1. 题目链接:
  2. 2. 题意:
  3. 3. 分析:
  4. 4. 代码: