BZOJ 1396 识别子串

BZOJ 1396 识别子串

昨晚拿到这道题想到了线段树做法还以为麻烦了,码了好久过了才发现网上都这么写的。。

只出现一次实际上就是 endpos 集合大小为1,就是 parent 树上siz是1。

由于我们只需要 endpos 集合大小是1的点的 endpos 集合,也没必要线段树合并求 endpos 集合了,对每个点加进去的时候记录一下 endpos 。由于我们只需要集合大小为 1 的,更新覆盖一下没关系。

然后现在拿到这些点后,假设这些点的 endpos 为$en$,这个点上最长串长度为$len$最短串为$minlen = len[par[u]] + 1$,其对于$en - minlen + 1$到$en$这一段贡献是$minlen$对于$en - len$到$en - minlen$的贡献是一个一次函数($en - pos$),其实这个一次函数我们只需要记录$en$,最后也只需要找到最小的$en$就好了。

可以开两棵线段树做,其实也可以用$set$类似差分的做吧,不过线段树毕竟很板子。(只是码得多一点)

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define MAXN 200006

int n , lst , m;
char ch[MAXN];
int ans[MAXN];

struct seg {
int T[100000 << 2] , lz[100000 << 2];
void build( ) {
memset( T , 0x3f , sizeof T ) , memset( lz , 0x3f , sizeof lz );
}
void pd( int rt ) {
if( lz[rt] != 0x3f3f3f3f ) {
T[rt << 1] = min( T[rt << 1] , lz[rt] );
T[rt << 1 | 1] = min( T[rt << 1 | 1] , lz[rt] );
lz[rt << 1] = min( lz[rt << 1] , lz[rt] );
lz[rt << 1 | 1] = min( lz[rt << 1 | 1] , lz[rt] );
lz[rt] = 0x3f3f3f3f;
}
}
void chkmn( int rt , int l , int r , int L , int R , int c ) {
if( L <= l && R >= r ) { lz[rt] = min( lz[rt] , c ) , T[rt] = min( T[rt] , c ); return; }
pd( rt );
int m = l + r >> 1;
if( L <= m ) chkmn( rt << 1 , l , m , L , R , c );
if( R > m ) chkmn( rt << 1 | 1 , m + 1 , r , L , R , c);
}
void getit( int rt , int l , int r ) {
if( l == r ) { ans[l] = min( ans[l] , T[rt] ); return; }
pd( rt );
int m = l + r >> 1;
getit( rt << 1 , l , m ) , getit( rt << 1 | 1 , m + 1 , r );
}
} T[2] ;

struct SAM{
int son[MAXN][27]; // sons
int par[MAXN] , len[MAXN]; // node
int head[MAXN] , nxt[MAXN<<1] , to[MAXN<<1]; // edge
int cnt , ecnt;
int s[MAXN];
void adde( int u , int v ) {
to[++ecnt] = v;
nxt[ecnt] = head[u];
head[u] = ecnt;
}
void init( ) {
memset( son , 0 , sizeof son ) , memset( head , -1 , sizeof head );
cnt = lst = 1; ecnt = 0;
}
void addall( ) {
for( int i = 2 ; i <= cnt ; ++ i ) adde( par[i] , i );
}
int en[MAXN];
void ins( int x , int i ) {
int cur = ++ cnt; en[cur] = i;
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;
en[cl] = en[q];
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;
}
void dfs( int u ) {
if( head[u] == -1 ) {
int t = en[u] , l = len[u] , l1 = len[par[u]];
T[0].chkmn( 1 , 1 , n , t - l1 + 1 , t , l1 );
T[1].chkmn( 1 , 1 , n , t - l + 1 , t - l1 , t );
}
for( int i = head[u] ; ~i ; i = nxt[i] ) {
int v = to[i];
dfs( v );
}
}
} S ;
namespace wtf {

int main() {
S.init();
scanf("%s",ch + 1);
n = strlen( ch + 1 );
S.init( );
for( int i = 1 ; i <= n ; ++ i ) S.ins( ch[i] - 'a' , i );
T[0].build() , T[1].build();
S.addall();
S.dfs( 1 );
memset( ans , 0x3f , sizeof ans );
T[1].getit( 1 , 1 , n );
for( int i = 1 ; i <= n ; ++ i ) {
ans[i] = ans[i] - i;
}
T[0].getit( 1 , 1 , n );
for( int i = 1 ; i <= n ; ++ i )
printf("%d\n",ans[i] + 1);
}
}
int main() {
wtf::main();
}
文章作者: yijan
文章链接: https://yijan.co/old37/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog