AUOJ415 s2mple 的字符串

一个我没写过的套路。

这个题目其实就是问你给你一个串,可以往前添加一些字符,往后添加一些字符,有多少种添加方式使得最终串不同。

我们先考虑向前添加字符,不难发现一个字符串向前添加字符可以得到的就是 parent 树子树内的本质不同的所有字符串。设这个串长为 $|S|$ ,子树内的本质不同串的个数为 $a$ ,当前点上最短串长为 $b$ ,那么添加方案数就是 $a+b-|S|$ 。

我们考虑往后添加字符的情况,往后添加一个字符就是在 SAMDAG 往后走一步。所以如果我们设往后添加了 $k$ 个字符,此时往后走到了 $u$ 这个点,那么往前添加的方案数就是 $a_u+b_u - (|S|+k)$ 这个值。不难发现我们对所有它在 DAG 上的后继节点求和这个之后得到的是一个关于 $|S|$ 的一次函数。所以我们考虑维护这个一次函数,具体来说,我们先把 parent 树上的 $dp$ 做好,求出每个节点的 $a,b$ 然后令 $k_u=-1,b_u=a+b$ ,然后再在 DAG 上做第二个 $dp$ ,具体来说是 k[u] += k[v] , b[u] += k[v] + b[v] ,因为往后一步后长度增加了 $1$ 。

复杂度就是建 SAM 的复杂度。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 800006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , q;
char ch[MAXN];

struct SAM {
int son[MAXN][26] , par[MAXN] , len[MAXN] , cnt , las;

SAM() { cnt = las = 1; }

void ins( char a ) {
int x = a - 'a' , cur = ++ cnt , p = las;
len[cur] = len[p] + 1;
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 ct = ++ cnt;
len[ct] = len[p] + 1 , par[ct] = par[q];
memcpy( son[ct] , son[q] , sizeof son[q] );
par[cur] = par[q] = ct;
for( ; son[p][x] == q ; p = par[p] ) son[p][x] = ct;
}
}
las = cur;
}

vi G[MAXN];
void addall( ) {
rep( i , 2 , cnt ) G[par[i]].pb( i );
}

ll S[MAXN] , k[MAXN] , b[MAXN];
int g[MAXN][20];
void dfs( int u ) {
S[u] = len[u] - len[par[u]];
for( int v : G[u] ) {
g[v][0] = u;
rep( k , 1 , 18 ) if( g[g[v][k - 1]][k - 1] ) g[v][k] = g[g[v][k - 1]][k - 1]; else break;
dfs( v );
S[u] += S[v];
}
k[u] = -1 , b[u] = S[u] + len[par[u]] + 1;
}

int deg[MAXN] , A[MAXN] , cn;
void wkr( ) {
addall( );
dfs( 1 );
rep( i , 1 , cnt ) rep( k , 0 , 25 ) if( son[i][k] ) ++ deg[son[i][k]];
queue<int> Q;
Q.push( 1 );
while( !Q.empty() ) {
int u = Q.front() , v; Q.pop();
A[++ cn] = u;
rep( k , 0 , 25 ) if( ( v = son[u][k] ) && !( --deg[v] ) )
Q.push( v );
}
reverse( A + 1 , A + 1 + cn );
rep( i , 1 , cn ) {
int u = A[i] , v;
rep( t , 0 , 25 ) if( v = son[u][t] )
k[u] += k[v] , b[u] += b[v] + k[v];
}
}
int jump( int u , int l ) {
per( k , 18 , 0 ) if( g[u][k] && l <= len[g[u][k]] ) u = g[u][k];
return u;
}
} S ;

int ps[MAXN];

void solve() {
cin >> n >> q;
scanf("%s",ch + 1);
rep( i , 1 , n ) S.ins( ch[i] ) , ps[i] = S.las;
S.wkr( );
rep( i , 1 , q ) {
int l , r;
scanf("%d%d",&l,&r);
int u = S.jump( ps[r] , r - l + 1 );
printf("%lld\n",S.k[u] * ( r - l + 1 ) + S.b[u]);
}
}

signed main() {
// int T;cin >> T;while( T-- ) solve();
solve();
}

文章作者: yijan
文章链接: https://yijan.co/2021/04/22/auoj415-s2mple-de-zi-fu-chuan/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog