YbtOJ #544. 「后缀自动机」子串选取
本文最后更新于 100 天前,其中的信息可能已经有所发展或是发生改变。

题目链接: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

#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;
}

评论

  1. 275307894a
    Windows Chrome 89.0.4389.90
    3月前
    2022-2-10 16:54:48

    SAM+线段树凭什么没人权/fn/fn

    • 博主
      275307894a
      Windows Chrome 98.0.4758.82
      3月前
      2022-2-11 14:58:03

      因为跑得慢!(即答

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇