题意翻译

给出一个长度为$n$的字符串$s[1]$，由小写字母组成。定义一个字符串序列$s[1....k]$,满足性质：$s[i]$在$s[i-1]$ $(i>=2)$中出现至少两次（位置可重叠），问最大的$k$是多少，使得从$s[1]$开始到$s[k]$都满足这样一个性质。

题解

　　看了一个中午的代码终于弄懂了……$yyb$大佬强无敌……

　　一开始以为是SAM建好之后直接上$dp$，直接用$parent$树上的儿子节点更新父亲，因为parent树上节点不同说明出现次数必定不同。但交上去一发WA了。才发现自己这种想法不能保证$parent$树上的父亲必定在儿子中出现过超过两次……

　　还是来说说正解吧。我们先对原串建好SAM，并记录下每一个节点的任意一个$endpos$。考虑一下如何判断一个串是否在另一个串中出现，如果一个串（设串$A$）在另一个串（设串$B$）中出现了大于等于两次，那么在原串的任意位置的串$B$中都出现了两次。

　　于是考虑一下维护每一个点的$endpos$集合，这个只要用线段树就行了。如果$A$在$B$中出现了两次，那么$A$的$endpos$集合在$[pos[B]-len[B]+len[A],pos[B]]$中出现了至少两次（其中$pos[B]$表示$B$的任意一个$endpos$）。

　　不难发现有一个$dp$，每一个$parent$树上的父亲节点都可能转移到儿子节点，于是从上到下$dp$。又因为$parent$树上父亲是儿子的严格后缀，所以必然在儿子里出现了一次，那么只要考虑$endpos[A]$中是否有元素在$[pos[B]-len[B]+len[A],pos[B]-1]$中就行了

1 //minamoto 2 #include
     
       3 #include
      
        4 using namespace std; 5 template
       
        inline bool cmax(T&a,const T&b){
   return a
        
         >1;33     if(x<=mid) modify(L[now],l,mid,x);34     else modify(R[now],mid+1,r,x);35 }36 int merge(int x,int y){37     if(!x||!y) return x|y;38     int z=++tot;39     L[z]=merge(L[x],L[y]);40     R[z]=merge(R[x],R[y]);41     return z;42 }43 int query(int x,int l,int r,int ql,int qr){44     if(!x) return 0;if(ql<=l&&qr>=r) return 1;45     int mid=l+r>>1;46     if(ql<=mid&&query(L[x],l,mid,ql,qr)) return 1;47     if(qr>mid&&query(R[x],mid+1,r,ql,qr)) return 1;48     return 0;49 }50 int main(){51     scanf("%d",&n);52     scanf("%s",s+1);53     for(int i=1;i<=n;++i) ins(s[i]-'a',i),modify(rt[last],1,n,i);54     calc();55     for(int i=cnt;i>1;--i) rt[fa[a[i]]]=merge(rt[fa[a[i]]],rt[a[i]]);56     for(int i=2;i<=cnt;++i){57         int u=a[i],ff=fa[u];58         if(ff==1){f[u]=1,top[u]=u;continue;}59         int x=query(rt[top[ff]],1,n,pos[u]-l[u]+l[top[ff]],pos[u]-1);60         if(x) f[u]=f[ff]+1,top[u]=u;61         else f[u]=f[ff],top[u]=top[ff];62         cmax(ans,f[u]);63     }64     printf("%d\n",ans);65     return 0;66 }