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<bits/stdc++.h>

#define ll long long

#define N 400005

using 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<l) return 0;

	if(l<=lx&&rx<=r) return tag[v];

	int mid=lx+rx>>1;

	return query(ls[v],lx,mid,l,r)+query(rs[v],mid+1,rx,l,r);

}

vector<int>e[N<<1];

void dfs(int v) {

	if(pos[v]) Insert(rt[v],rt[v],lx,rx,pos[v]);

	for(int i=0;i<e[v].size();i++) {

		int to=e[v][i];

		dfs(to);

		pos[v]=pos[to];

		rt[v]=Merge(rt[v],rt[to],lx,rx);

	}

}

int f[N],top[N];

int ans;

bool chk(int v,int f) {

	return query(rt[f],lx,rx,pos[v]-mxlen[v]+mxlen[f],pos[v])>=2;

}

void solve(int v) {

	ans=max(ans,f[v]);

	for(int i=0;i<e[v].size();i++) {

		int to=e[v][i];

		if(v==1) f[to]=1,top[to]=to;

		else {

			if(chk(to,top[v])) f[to]=f[v]+1,top[to]=to;

			else f[to]=f[v],top[to]=top[v];

		}

		solve(to);

	}

}

int main() {

	n=Get();

	scanf("%s",s+1);

	lx=1,rx=n;

	for(int i=1;i<=n;i++) Insert(s[i]-'a',i);

	for(int i=2;i<=cnt;i++) {

		e[fail[i]].push_back(i);

	}

	dfs(1);

	solve(1);

	cout<<ans;

	return 0;

}