【SP8222】NSUBSTR

Source and Judge

SP8222
luoguSP8222

Record

1h

Analysis

请先思考后再展开

模板练手好题

方法一:
后缀数组+并查集,xgc大佬教的新姿势
先明确,它一定是递减的,而且如果前面某个长度出现过,那么后面也会出现
核心思路:如果某个答案出现至少两次,一定会被两个不同的前缀的lcp覆盖
想象在字典序排名上,相邻两个后缀之间的间隔,逐渐消失
那么用并查集维护最大联通块即可

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
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#ifdef DEBUG
const int LOCAL=1;
#else
const int LOCAL=0;
#endif
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
int qread()
{
int ans=0,f=1;char c=getchar();
while(c<'0' or c>'9') {if(c=='-') f=-1;;c=getchar();}
while(c>='0' and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
const int MAX_N=310000;
char str[MAX_N];int len;
struct Sa
{
int sa[MAX_N],tmp[MAX_N];
int rk[2*MAX_N],rk2[2*MAX_N];//两倍
int ct[MAX_N];
bool diff(int a,int b,int ln) {return rk2[a]!=rk2[b] or rk2[a+ln]!=rk2[b+ln];}
void build()
{
memset(ct,0,sizeof ct);
for(int i=1;i<=len;i++) ct[rk[i]=str[i]]++;
for(int i=1;i<=MAX_N;i++) ct[i]+=ct[i-1];
for(int i=len;i>=1;i--) sa[ct[rk[i]]--]=i;
int ln=1;
while(ln<len)
{
int cnt=0;for(int i=len-ln+1;i<=len;i++) tmp[++cnt]=i;
for(int i=1;i<=len;i++) if(sa[i]-ln>=1) tmp[++cnt]=sa[i]-ln;
memset(ct,0,sizeof ct);
for(int i=1;i<=len;i++) ct[rk[tmp[i]]]++;
for(int i=1;i<MAX_N;i++) ct[i]+=ct[i-1];
for(int i=len;i>=1;i--) sa[ct[ rk[tmp[i]] ]--]=tmp[i];
cnt=0;memcpy(rk2,rk,sizeof rk);
for(int i=1;i<=len;i++)
{
if(diff(sa[i-1],sa[i],ln)) cnt++;
rk[sa[i]]=cnt;
}
ln*=2;
}
}
int hei[MAX_N];
void geth()
{
int lst=0;
for(int i=1;i<=len;i++)
{
if(rk[i]==1) {hei[1]=0;continue;}
if(lst) lst--;
while(max(i,sa[rk[i]-1])+lst<=len and str[sa[rk[i]-1]+lst]==str[i+lst]) lst++;
hei[rk[i]]=lst;
}
}
}sa;
struct Dsu
{
int fa[MAX_N],siz[MAX_N];
int mx;Dsu(){mx=1;}
int findfa(int x) {return fa[x]=(fa[x]==x?x:findfa(fa[x]));}
void join(int x,int y)
{
int fx=findfa(x),fy=findfa(y);
if(fx!=fy)
{
fa[fy]=fx;
siz[fx]+=siz[fy];
if(siz[fx]>siz[mx]) mx=fx;
}
}
}dsu;
int ss[MAX_N];bool cmp(int a,int b) {return sa.hei[a]<sa.hei[b];}
int dp[MAX_N];
void main()
{
scanf("%s",str+1);
len=strlen(str+1);
sa.build();
sa.geth();
for(int i=1;i<=len;i++) ss[i]=i,dsu.fa[i]=i,dsu.siz[i]=1;
sort(ss+1,ss+len+1,cmp);
for(int now=len;now>=1;now--)
{
dsu.join(sa.sa[ss[now]],sa.sa[ss[now]-1]);
dp[ sa.hei[ss[now]] ]=max(dp[ sa.hei[ss[now]] ],dsu.siz[dsu.mx]);
}
dp[len]=1;for(int k=len-1;k>=1;k--) dp[k]=max(dp[k],dp[k+1]);
for(int i=1;i<=len;i++) printf("%d\n",dp[i]);
}
};
int main()
{
srand(time(0));
mine::main();
}

方法二:
sam,建出parent树
在树上做一次dp,right集合意味着出现次数,影响的答案范围是min~max
又因为上面提到的性质,不用写数据结构更新,只修改max,最后更新一下即可

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
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
int qread()
{
int ans=0,f=1;char c=getchar();
while(c<'0' or c>'9') {if(c=='-') f=-1;;c=getchar();}
while(c>='0' and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
const int MAX_N=310000;
int ans[MAX_N];
char str[MAX_N];int len;
struct Sam
{
struct Nod
{
int son[30];
int mx,nxt;
int right;
Nod() {memset(son,0,sizeof son);mx=nxt=0;right=0;}
}p[MAX_N*2];
int id,lst;Sam() {id=1;lst=1;}//rt=1 null=0
void add(int c)
{
int now=++id;
p[now].mx=p[lst].mx+1;
int a;for(a=lst;a!=0 and p[a].son[c]==0;a=p[a].nxt) p[a].son[c]=now;
if(a==0) p[now].nxt=1;
else
{
int b=p[a].son[c];
if(p[a].mx+1==p[b].mx) p[now].nxt=b;
else
{
int tmp=++id;p[tmp]=p[b];
p[tmp].mx=p[a].mx+1;
p[b].nxt=p[now].nxt=tmp;
for(;p[a].son[c]==b;a=p[a].nxt) p[a].son[c]=tmp;
}
}
lst=now;
}
int tt[MAX_N*2];
void solve()
{
for(int i=1,now=1;i<=len;i++)
{
now=p[now].son[str[i]-'a'];
p[now].right++;
}
for(int i=id;i>=1;i--)
{
int now=tt[i];
p[p[now].nxt].right+=p[now].right;
ans[p[now].mx]=max(ans[p[now].mx],p[now].right);
}
}
}sam;
bool cmp(int a,int b) {return sam.p[a].mx<sam.p[b].mx;}
void main()
{
scanf("%s",str+1);len=strlen(str+1);
for(int i=1;i<=len;i++) sam.add(str[i]-'a');
for(int i=1;i<=sam.id;i++) sam.tt[i]=i;
sort(sam.tt+1,sam.tt+sam.id+1,cmp);
sam.solve();
ans[len]=1;for(int i=len-1;i>=1;i--) ans[i]=max(ans[i],ans[i+1]);
for(int i=1;i<=len;i++) printf("%d\n",ans[i]);
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/d300.html
转载请注明出处,谢谢!