【题解】SP1812 【LCS2 - Longest Common Substring II 】

\(\text{Suffix Tree:}\)我来啦我来啦

\(\text{Solution:}\)

题目要求求好几个串串的\(\text{LCS.}\)

由于串串的数量并不多，所以我们把它们塞到一个\(\text{Suffix Tree}\)里面，中间加上分隔符号。

那么答案就是最深的且它的子树中具有所有分节符的非叶子节点。

至于分节符数量和种类，用前缀和即可。

介于\(\text{Suffix Tree}\)压缩的性质，菜鸡笔者还不太清楚一边插入一边维护的方法，求指教。

前缀和维护的原理：由于最前面的绝对先出现，所以从第一个枚举到最后一个，看看这个区间中是不是有这个串串的分节符。如果有，跳出即可。因为它所代表的后缀只属于这一个串串。

至于如何判断这些分节符是不是都有，用了状压。\(\text{1<<i}\)表示第\(i\)个分节符有没有，统计的时候用或运算即可。

话说\(\text{Fread}\)可以读入这种非固定数量的字符咩？

#include<bits/stdc++.h>

#include<ctime>

using namespace std;

const int MAXN=2e6+10;

char Z[20][100001];

int n,val[MAXN],ans,M,tot,num;

int sum[20][MAXN];

const int inf=(1<<30);

struct SuffixTree {

	int link[MAXN],ch[MAXN][50],now,rem,n;

	int start[MAXN],len[MAXN],tail,s[MAXN];

	SuffixTree() {

		tail=now=1;

		rem=n=0;

		len[0]=inf;

	}

	inline int build(int a,int b) {

		link[++tail]=1;

		start[tail]=a;

		len[tail]=b;

		return tail;

	}

	void Extend(int x) {

		s[++n]=x;

		++rem;

		for(int last=1; rem;) {

			while(rem>len[ch[now][s[n-rem+1]]])

				rem-=len[now=ch[now][s[n-rem+1]]];

			int &v=ch[now][s[n-rem+1]];

			int c=s[start[v]+rem-1];

			if(!v||x==c) {

				link[last]=now;

				last=now;

				if(!v)v=build(n,inf);

				else break;

			} else {

				int u=build(start[v],rem-1);

				ch[u][c]=v;

				ch[u][x]=build(n,inf);

				start[v]+=rem-1;

				len[v]-=rem-1;

				link[last]=v=u;

				last=u;

			}

			if(now==1)--rem;

			else now=link[now];

		}

	}

} T;

void predfs(int u,int dep) {

	if(dep>=inf) {

		int L=T.start[u];

		int R=L+T.len[u]-1;

		R=min(R,T.n);

		for(int i=1;i<=num;++i){

			if(sum[i][R]-sum[i][L-1]){

				val[u]|=(1<<i);

				break;

			}

		}

		return;

	}

	for(int i=0; i<=25+num; ++i) {

		if(T.ch[u][i]) {

			predfs(T.ch[u][i],dep+T.len[T.ch[u][i]]);

			val[u]|=val[T.ch[u][i]];

		}

	}

	if(val[u]==M)ans=max(ans,dep);

}

int main() {

	while(scanf("%s",Z[++num]+1)!=EOF);

	num--;

	int G='0';int len=strlen(Z[1]+1);

	Z[1][++len]=(char)G;

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

		G++;

		int L=strlen(Z[i]+1);

		for(int j=1;j<=L;++j)Z[1][++len]=Z[i][j];

		Z[1][++len]=(char)G;

	}

	for(int i=1;i<=num;++i)M+=(1<<i);

	for(int i=1;i<=len;++i){

		if(Z[1][i]>='a')T.Extend(Z[1][i]-'a');

		else T.Extend(Z[1][i]-'0'+1+25);

	}

	for(int i=1;i<=len;++i){

		for(int j=1;j<=num;++j)sum[j][i]=sum[j][i-1];

		if(T.s[i]>25){

			int V=T.s[i]-25;

			sum[V][i]++;

		}

	}

	predfs(1,0);

	cout<<ans<<endl;

	return 0;

}

注意，分节符不要超过\(\text{ASCII}\)表的范围，不然喜提\(RE.\)

巴特西

【题解】SP1812 【LCS2 - Longest Common Substring II 】

最新文章

热门文章