YbtOJ 544「后缀自动机」子串选取

(Updated: )
oi
, , , ,

题目链接：YbtOJ #544

小 A 有一个长度为 $n$ 的小写字母串 $s$。

你可以从左到右依次 选出 若干个 无交 子串 $t_1,t_2,\cdots,t_m$，要求每次选出的字符串 $t_i$ 必须是前一个字符串 $t_{i-1}$ 的 真子串（即 $t_i$ 是 $t_{i-1}$ 的子串且 $t_i$ 的长度比 $t_{i-1}$ 小）。

小 A 想要知道一次最多能选出多少个子串（即选出的 $m$ 最大是多少）。

$1\le n\le5\times10^5$。

Solution

不妨把串翻转，那么就变成每次在上一个子串的基础上左右任添加字符。

容易发现答案最大只有 $\sqrt{2n}$，并且贪心地想子串的长度必然依次为 $1,2,3,\cdots,Ans$。

设 $f_i$ 表示当前答案 $Ans$ 下以 $i$ 为末尾的后缀是否可行。

按顺序枚举，转移时判断 $[i-Ans+2,i]$ 与 $[i-Ans+1,i-1]$ 的出现情况即可，注意该子串需要为 $i-Ans$ 前的。

注意到 $i-Ans$ 单调不减，所以在每次 $Ans$ 减少时加入原来 $i-Ans$ 为末尾的合法子串。

注意到任意时刻 Hash Table 中有用的字符串长度相同，所以动态维护即可。

据说单模也能过，于是我试着换成了单模结果又wa又T的。

然后这道题 SAM+线段树 也是能做的，只需要一只 $\log$，但是常数大跑得比根号还慢/cy。

Code

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
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
Cn int N=5e5+10,M=sqrt(2*N);
int n,a[N],OW[2][N],Ans,f[N];char s[N];
struct Base{int pw,md;}o[2];
struct HashX{int x,y;}h[N];
I HashX operator+(Cn HashX& A,CI v){return (HashX){(1LL*A.x*o[0].pw%o[0].md+v)%o[0].md,(1LL*A.y*o[1].pw%o[1].md+v)%o[1].md};}
I bool operator==(Cn HashX& A,Cn HashX& B){return A.x==B.x&&A.y==B.y;}
I HashX Hash(CI l,CI r){return (HashX){(h[r].x+o[0].md-1LL*h[l-1].x*OW[0][r-l+1]%o[0].md)%o[0].md,(h[r].y+o[1].md-1LL*h[l-1].y*OW[1][r-l+1]%o[1].md)%o[1].md};}
#define PA pair<int,int>
#define MP make_pair
#define fi first
#define se second
vector<PA> q[N];
#define pb push_back
I bool operator<(Cn HashX& A,Cn HashX &B){return A.x^B.x?A.x<B.x:A.y<B.y;}
map<HashX,bool> mp[M];
struct HashTable{
    int fir[19260818],nxt[N*4],val[N*4],w[N*4],tot;
    I void Add(Cn HashX& z){nxt[++tot]=fir[z.x],fir[z.x]=tot,w[tot]=z.y;}
    I int Q(Cn HashX& z){RI i;for(i=fir[z.x];i;i=nxt[i]) if(w[i]==z.y) return 1;return 0;}
}H;
int main(){
    freopen("substr.in","r",stdin),freopen("substr.out","w",stdout);
    RI i,j,mx,t;for(scanf("%d",&n),mx=sqrt(2*n),scanf("%s",s+1),o[0]=(Base){233,19260817},o[1]=(Base){31,19260817},i=1;i<=n;i++) a[i]=s[n-i+1]-'a'+1,h[i]=h[i-1]+a[i];
    for(OW[0][0]=OW[1][0]=i=1;i<=n;i++) OW[0][i]=1LL*OW[0][i-1]*o[0].pw%o[0].md,OW[1][i]=1LL*OW[1][i-1]*o[1].pw%o[1].md;for(H.Add((HashX){0,0}),i=1;i<=n;i++){
        for(t=f[i-1]+1;!H.Q(Hash(i-t+2,i))&&!H.Q(Hash(i-t+1,i-1));){
            t--;for(j=f[i-t];j>=1&&!H.Q(Hash(i-t-j+1,i-t));j--) H.Add(Hash(i-t-j+1,i-t));
        }Ans=max(Ans,(f[i]=t));
    }return printf("%d\n",Ans),cerr<<clock()<<'\n',0;
}