目录

  1. 引言
  2. BZOJ 4502: 串
    1. Description
    2. Input
    3. Output
    4. Sample Input
    5. Sample Output
    6. HINT
    7. 题目分析
    8. 代码

引言

BZOJ 4502: 串 题解

BZOJ 4502: 串

  • Time Limit: 30 Sec

  • Memory Limit: 512 MB

Description

兔子们在玩字符串的游戏。首先,它们拿出了一个字符串集合S,然后它们定义一个字
符串为“好”的,当且仅当它可以被分成非空的两段,其中每一段都是字符串集合S中某个字符串的前缀。
比如对于字符串集合{“abc”,”bca”},字符串”abb”,”abab”是“好”的(”abb”=”ab”+”b”,abab=”ab”+”ab”),而字符串“bc”不是“好”的。
兔子们想知道,一共有多少不同的“好”的字符串。

Input

第一行一个整数n,表示字符串集合中字符串的个数
接下来每行一个字符串

Output

一个整数,表示有多少不同的“好”的字符串

Sample Input

2

ab

ac

Sample Output

9

HINT

1<=n<=10000,每个字符串非空且长度不超过30,均为小写字母组成。

题目分析

字符串好题

对于这样的一些多串问题,我们第一反应就是建出Trie树

然后,有了Trie树,我们继续观察题目性质

我们首先可以把所有的前缀两两有序组合,这样现在一共有$n ^ 2$个组合,我们考虑如何舍去其中重复的那些

我们规定,对于所有重复的组合,我们只保留第二个前缀长度最大的那个

这样,如果一个组合被舍弃了,我们能够知道,这是因为,这个组合的后一个前缀被真包含于一个更长的前缀,而且这个前缀可以和其他的前缀重新形成一样的组合

我们现在就要对每个前缀统计它能够舍掉多少个组合数量,我们定义一个组合被它所舍弃掉,当且仅当这个组合的第二个前缀是它的真后缀(如上面所说)并且能形成原来的组合,而且不存在另外一个满足前述条件的前缀真包含这个前缀,因为更短的前缀形成的组合会被其他的串舍弃掉

注意上面讨论的前缀都是作为第二个前缀存在于组合中的,而且其实上面的定义是为了更好的适用于AC自动机的失配边(就是说,其实是先想到了AC自动机,才要这样做的…..)

我们发现,对于一个前缀,我们需要找到它的最大的后缀,满足这个后缀在前缀集合中出现,所以我们需要建出AC自动机,然后沿着它的失配边走一次就能得到我们想要的这个前缀

我们知道,这会带来一个长度上的差值$d$,这告诉我们,所有长度大于$d$的前缀作为第一个前缀与这个较短的前缀组合的话,都是会被原前缀舍弃掉的,原因请自行思考

其实是这样的,你可以把第二个前缀加长到原前缀,然后前面的缩减$d$的长度,这样一定也是一种已经存在的组合

所以,我们只要对每个前缀都统计出需要舍掉多少,然后直接用$n ^ 2$减掉,就是最终答案了

好像比网上的DP快了6000多ms?

代码

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
/**************************************************************
Problem: 4502
User: Renatus
Language: C++
Result: Accepted
Time:4452 ms
Memory:481016 kb
****************************************************************/
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cassert>
#define maxs 105
#define maxn 405005
#define ll long long int
#define rep(i, l, r) for (register int i = l; i <= r; i++)
#define per(i, r, l) for (register int i = r; i >= l; i--)
using namespace std;
int n, len;
char s[maxs];
namespace Trie{
#define sigma 26
struct node{
node* ch[sigma];
int siz, tsiz;
node(int siz = 0, int tsiz = 0) {rep(i, 0, sigma - 1) ch[i] = NULL;}//注意即使预先留了0的空位值,但是如果不赋上去的话也是没有用的
}*root;
void insert(node*& now, int pos){
if (!now) now = new node(), now -> siz = now -> tsiz = 0;
now -> siz++;
if (pos < 0) {now -> tsiz++; return;}
if (s[pos] - 'a' >= sigma) assert(false);
insert(now -> ch[s[pos] - 'a'], pos - 1);
}
int get_siz(node* now, int pos){
if (!now) return 0;
if (pos < 0) return now -> siz - now -> tsiz;
if (s[pos] - 'a' >= sigma) assert(false);
return get_siz(now -> ch[s[pos] - 'a'], pos - 1);
}
}using namespace Trie;
ll ans = 0;
namespace AC_automaton{
#define sigma 26
int ch[maxn][sigma];
int d[maxn];
int f[maxn];
int ct = 0;
queue<int> bfs;
void insert(){
int now = 0;
rep(i, 0, len - 1){
int& next = ch[now][s[i] - 'a'];
if (!next) next = ++ct, d[next] = d[now] + 1;
now = next;
}
}
void get_AC(){
f[0] = 0;
rep(i, 0, sigma - 1){
if (ch[0][i]) bfs.push(ch[0][i]), f[ch[0][i]] = 0;
}
while (!bfs.empty()){
int x = bfs.front(); bfs.pop();
rep(i, 0, sigma - 1){
if (!ch[x][i]) continue;
else{
int k = f[x];
while (k && !ch[k][i]) k = f[k];
f[ch[x][i]] = ch[k][i];
bfs.push(ch[x][i]);
}
}
}
}
void DFS(int x){
insert(root, len - 1);
rep(i, 0, sigma - 1){
if (!ch[x][i]) continue;
s[len++] = 'a' + i;
DFS(ch[x][i]);
len--;
}
}
void DFS2(int x){
int k = f[x];
if (k){
len -= d[k];
ans -= get_siz(root, len - 1);
len += d[k];
}
rep(i, 0, sigma - 1){
if (!ch[x][i]) continue;
s[len++] = 'a' + i;
DFS2(ch[x][i]);
len--;
}
}
}using namespace AC_automaton;
int main(){
#ifndef ONLINE_JUDGE
freopen("bunch.in", "r", stdin);
#endif
scanf("%d", &n);
rep(i, 1, n) {
scanf("%s", s);
len = strlen(s);
insert();
}
get_AC();
len = 0;
DFS(0);
ans = (ll)ct * ct;
len = 0;
DFS2(0);
printf("%lld", ans);
return 0;
}

细节:注意构造函数的正确使用方法