BZOJ 3277 串
首先建立广义SAM，然后考虑SAM上一个节点是多少个串的子串。
这是一个从 bzoj 2780 学来的做法，就是建立广义SAM后对于每一个串在SAM上跑出每个前缀所在的节点，这个可以直接转移，然后从这些节点分别跳parent，直到跳到一个已经被这个串以前的点跳到过的点，并把跳到的点所属的词++。
这样看上去很$O(n^2)$但实际上它跑的跟$O(n)$似的快。
不太会证明QAQ，有会证这个下界的评论一下吧～
现在我们可以再拿这些串跑一遍跑到的点如果拥有的词多余 k 我们就把它的所有 parent 树上祖先的拥有的词多余 k 的子串数和给得到。意思就是以某个字符串中的位置为后缀得到的所有满足条件的子串。可以一次dp算出来，也可以直接记忆化比较好写。
就酱
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
| #include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define MAXN 400006
int n , lst , m;
char ch[MAXN];
struct SAM{
int son[MAXN][27];
int par[MAXN] , len[MAXN];
int cnt;
int s[MAXN];
void init( ) {
memset( son , 0 , sizeof son );
cnt = lst = 1;
}
void ins( int x ) {
int cur = ++ cnt;
len[cur] = len[lst] + 1;
int p = lst;
while( p && !son[p][x] ) son[p][x] = cur , p = par[p];
if( !p ) par[cur] = 1;
else {
int q = son[p][x];
if( len[q] == len[p] + 1 ) par[cur] = q;
else {
int cl = ++ cnt;
memcpy( son[cl] , son[q] , sizeof son[q] );
par[cl] = par[q];
len[cl] = len[p] + 1 , par[q] = par[cur] = cl;
for( ; son[p][x] == q ; p = par[p] ) son[p][x] = cl;
}
}
lst = cur;
}
int vis[MAXN];
void add( int cur , int i ) {
++ s[cur] , vis[cur] = i;
if( par[cur] && vis[par[cur]] != i ) add( par[cur] , i );
}
int dp[MAXN];
long long work( int cur , int i ) {
if( dp[cur] ) return dp[cur];
long long ret = 0;
if( s[cur] >= m ) ret += len[cur] - len[par[cur]];
if( par[cur] ) return dp[cur] = ret + work( par[cur] , i );
return dp[cur] = ret;
}
} S ;
namespace wtf {
int brk[MAXN], len[MAXN];
void main() {
cin >> n >> m;
S.init();
int tot = 0;
for (int i = 1; i <= n; ++i) {
lst = 1;
brk[i] = tot;
scanf("%s", ch + tot), len[i] = strlen(ch + tot);
for (int j = 0; j < len[i]; ++j) S.ins(ch[tot + j] - 'a');
tot += len[i];
}
int cur;
for (int i = 1; i <= n; ++i) {
cur = 1;
for (int j = brk[i]; j < brk[i] + len[i]; ++j)
cur = S.son[cur][ch[j] - 'a'], S.add(cur, i);
}
memset( S.vis , 0 , sizeof S.vis );
for (int i = 1; i <= n; ++i) {
cur = 1;
long long res = 0;
for (int j = brk[i]; j < brk[i] + len[i]; ++j)
cur = S.son[cur][ch[j] - 'a'], res += S.work(cur, i);
printf("%lld ",res);
}
}
}
int main() {
wtf::main();
}
|
