作者:三千仇人-奈我何 | 来源:互联网 | 2023-05-17 18:09
题目链接\(Description\)给定一个字符串\(s[1]\)。一个字符串序列\(s[\]\)满足\(s[i]\)至少在\(s[i-1]\)中出现过两次(\(i\geq2\))。求最
题目链接
\(Description\)
给定一个字符串\(s[1]\)。一个字符串序列\(s[\ ]\)满足\(s[i]\)至少在\(s[i-1]\)中出现过两次(\(i\geq 2\))。求最大的\(k\),满足存在\(s[1]\sim s[k]\)。
\(Solution\)
一开始以为直接自底向上合并right,如果|right|>1就继续向上。这显然不对啊,这样出现次数>1不一定是在之前的子节点中出现次数>1。
如果串\(A\)出现在串\(B\)中两次,那么说明什么?用\(right(endpos)\)表示一个串出现位置的最右端点集合,则\(right(A)\)在\(B[right(B)-len(A),right(B)]\)中至少出现过两次。
而且对于在原串中在任意位置出现的\(B\),\(A\)都满足上面的条件。
所以我们随便找一个\(pos[B]=某一个right(B)\),\(A\)若在\(B\)中出现至少两次则满足\(right(A)\)在\(s[pos[B]-len(B)+len(A),pos[B]]\)中至少出现了两次(\(s\)为原串)。
所有节点的\(right\)我们可以通过线段树合并全部得到。
\(parent\)树上的父节点能转移到子节点。可以看出从上到下的DP,如果满足条件则更新,用\(B\)(子节点)作为新的\(A\)(下次匹配作为父节点);不满足条件则保留之前的\(A\)(之前的父节点 更优)。
因为父节点\(A\)已经至少在子节点\(B\)中出现过一次了,所以只需要查\(s[pos[B]-len(B)+len(A),pos[B]-1]\)中是否存在\(right(A)\)(\(A\)的线段树中在该区间是否有值)。
还是有一种神奇hash做法。。见CF status。
顺便还有一种SA做法:
//95ms 131900KB
#include
#include
#include
#include
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=2e5+5;
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
struct Segment_Tree
{
#define ls son[x][0]
#define rs son[x][1]
static const int S=N*2*25;//最好是4nlogn...
int tot,son[S][2];
void Insert(int &x,int l,int r,int p)
{
/*if(!x)*/ x=++tot;
if(l==r) return;
int m=l+r>>1;
if(p<=m) Insert(ls,l,m,p);
else Insert(rs,m+1,r,p);
}
bool Query(int x,int l,int r,int L,int R)
{
if(!x) return 0;
if(L<=l && r<=R) return 1;//有这个节点即可
int m=l+r>>1;
if(L<=m)
if(m1; x=A[--i]) root[fa[x]]=T.Merge(root[fa[x]],root[x]);
int ans=1;
for(int i=2,x=A[i],tp; i<=tot; x=A[++i])
{
if(fa[x]==1) {f[x]=1, top[x]=x; continue;}
tp=top[fa[x]];
if(T.Query(root[tp],1,n,pos[x]-len[x]+len[tp],pos[x]-1))
f[x]=f[tp]+1, top[x]=x, ans=std::max(ans,f[x]);
else f[x]=f[tp], top[x]=tp;
}
printf("%d\n",ans);
}
}sam;
int main()
{
sam.Solve();
return 0;
}