欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

省选专练之后缀自动机SPOJLCS2 - Longest Common Substring II

程序员文章站 2022-04-30 18:41:48
...

省选专练之后缀自动机SPOJLCS2 - Longest Common Substring II

这个是陈老师证明SA不能解决的问题之一

但实际这更像广义SAM

但是普通SAM也能A

首先同两个串的类似直接建

但是用一个数组存下来当前节点的权值

但是我太菜了

这里又一个广义后缀自动机的思想:

同层可能不更新

所以你需要跑一次topsort然后更新,

实际也简单,因为parent树上的节点都是较短的,他们一定成立,跟新step为权值就好了

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=4e5+100;
char S[N];
struct SAM{
	int LCS[N];
	int ans[N];
	int C[N];
	int R[N];
	struct Node{
		int pre;
		int step;
		int vis[26];
	}SA[N];
	int cnt,last,now;
	int LCSNOW;
	inline void Insert(char C){
		int p=last;
		int np=++cnt;
		last=np;
		SA[np].step=SA[p].step+1;
		for(;!SA[p].vis[C-'a'];p=SA[p].pre)SA[p].vis[C-'a']=np;
		if(!p)SA[np].pre=1;
		else{
			int q=SA[p].vis[C-'a'];
			if(SA[q].step==SA[p].step+1){
				SA[np].pre=q;
			}
			else{
				int nq=++cnt;
				SA[nq].step=SA[p].step+1;
				memcpy(SA[nq].vis,SA[q].vis,sizeof(SA[q].vis));
				SA[nq].pre=SA[q].pre;
				SA[q].pre=SA[np].pre=nq;
				for(;SA[p].vis[C-'a']==q;p=SA[p].pre)SA[p].vis[C-'a']=nq;
			}
		}
	}
	void Getans(char C){
		if(SA[now].vis[C-'a']){
			now=SA[now].vis[C-'a'];
			LCSNOW=LCSNOW+1;
		}
		else{
			for(;now&&!SA[now].vis[C-'a'];now=SA[now].pre);
			if(!now)now=1,LCSNOW=0;
			else{
				LCSNOW=SA[now].step+1;
				now=SA[now].vis[C-'a'];
			}
//			cout<<now<<" "<<C<<" "<<LCS[Id][pos]<<'\n';
		}
		LCS[now]=max(LCS[now],LCSNOW);
//		cout<<LCSNOW<<'\n';
	}
	void Solve(){
		memset(ans,0x3f,sizeof(ans));
		cnt=last=1;
		scanf("%s",S+1);
		int len,Id=0,maxlen;
		len=strlen(S+1);
		maxlen=len;
		for(int i=1;i<=len;i++)Insert(S[i]);
		for(int i=1;i<=cnt;i++)C[SA[i].step]++;
		for(int i=1;i<=len;i++)C[i]+=C[i-1];
		for(int i=1;i<=cnt;i++)R[C[SA[i].step]--]=i;
		while(~scanf("%s",S+1)){
			memset(LCS,0,sizeof(LCS));
			++Id;
			now=1;
			LCSNOW=0;
			len=strlen(S+1);
			for(int i=1;i<=len;i++){
				Getans(S[i]);
			}
			for(int i=cnt;i>=1;i--){
				if(LCS[R[i]])LCS[SA[R[i]].pre]=SA[SA[R[i]].pre].step;
			}
			for(int i=cnt;i>=1;i--){
				ans[i]=min(ans[i],LCS[i]);
			}
		}
		int sum=-1;
		for(int i=1;i<=cnt;i++){
//			cout<<ans[i]<<'\n';
			sum=max(sum,ans[i]);
		}
		cout<<sum<<'\n';
	}
}Solution;
int main(){
//	freopen("spoj1812.in","r",stdin);
	Solution.Solve();
//	cout<<1;
	return 0;
}