CF700E Cool Slogans

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

很妙的题啊。

首先\(s[i]\)一定是\(s[i+1]\)的后缀。因为如果不是，我们可以吧多余的部分删除，这样不影响答案。

我们建出后缀自动机，然后在\(fail\)树上\(DP\)。我们设\(f_v\)表示后缀自动机上\(v\)节点代表的子串作为最后一个串的答案。

更新的时候就判断\(v\)的\(fail\)代表的节点是否在\(v\)代表的节点中出现了两次，如果是，\(f_v=f_{fail_v}+1\)。否则，\(v\)就没用了，我们更新\(v\)的儿子时仍然用\(fail_v\)来更新，因为他们\(f\)值相同，但是\(fail_v\)更短，所以更优。

判断一个串是否再另一个串中出现了两次可以用线段树合并搞一搞。

代码：

#include
    
     #define ll long long#define N 400005using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n;char s[N];int mxlen[N<<1],fail[N<<1];int ch[N<<1][26];int last=1,cnt=1;int pos[N<<1];void Insert(int f,int Pos) {    int p=last,v=++cnt;    pos[v]=Pos;    last=v;    mxlen[v]=mxlen[p]+1;    while(p&&!ch[p][f]) ch[p][f]=v,p=fail[p];    if(!p) return fail[v]=1,void();    int sn=ch[p][f];    if(mxlen[sn]==mxlen[p]+1) return fail[v]=sn,void();    int New=++cnt;    memcpy(ch[New],ch[sn],sizeof(ch[sn]));    mxlen[New]=mxlen[p]+1;    fail[New]=fail[sn];    fail[sn]=fail[v]=New;    while(p&&ch[p][f]==sn) ch[p][f]=New,p=fail[p];}int rt[N<<1];int lx,rx;int tot;int tag[N*40];int ls[N*40],rs[N*40];int mn[N<<1];void Insert(int &v,int old,int lx,int rx,int p) {    v=++tot;    tag[v]=tag[old]+1;    if(lx==rx) return ;    int mid=lx+rx>>1;    if(p<=mid) Insert(ls[v],ls[old],lx,mid,p);    else Insert(rs[v],rs[old],mid+1,rx,p);}int Merge(int a,int b,int lx,int rx) {    if(!a||!b) return a+b;    int v=++tot;    tag[v]=tag[a]+tag[b];    if(lx==rx) return v;    int mid=lx+rx>>1;    ls[v]=Merge(ls[a],ls[b],lx,mid);    rs[v]=Merge(rs[a],rs[b],mid+1,rx);    return v;}int query(int v,int lx,int rx,int l,int r) {    if(!v||lx>r||rx
     
      >1;    return query(ls[v],lx,mid,l,r)+query(rs[v],mid+1,rx,l,r);}vector
      
       e[N<<1];void dfs(int v) {    if(pos[v]) Insert(rt[v],rt[v],lx,rx,pos[v]);    for(int i=0;i
       
        =2;}void solve(int v) {    ans=max(ans,f[v]);    for(int i=0;i