【POJ2774】Long Long Message（后缀数组求Height数组）

点此看题面

大致题意： 求两个字符串中最长公共子串的长度。

关于后缀数组

关于\(Height\)数组的概念以及如何用后缀数组求\(Height\)数组详见这篇博客：后缀数组入门（二）——Height数组与LCP。

大致思路

由于后缀数组是处理一个字符串的，因此我们第一步自然是将这两个字符串拼在一起，并在中间加一个不可能出现的字符，例如\(\%\)。

然后我们用后缀数组求出其\(Height\)数组。

注意一个性质，答案肯定是按字典序排名后相邻后缀的\(LCP\)值中的最大值。

因此，我们只要枚举\(i\)，判断后缀\(_{SA_i}\)与后缀\(_{SA_{i-1}}\)的起始字符是否在同一个字符串内，然后更新答案即可。

回顾\(Height\)数组定义就是\(Height_i=LCP(i,i-1)\)。

因此我们其实不用再额外去求相邻后缀的\(LCP\)，直接调用\(Height\)数组即可。

具体实现详见代码。

代码

#include<cstdio>

#include<cstring>

#define N 100000

#define Gmax(x,y) (x<(y)&&(x=(y)))

using namespace std;

int n,m;char s[(N<<1)+5];

class Class_SuffixArray//后缀数组

{

	private:

		int n,rk[(N<<1)+5],pos[(N<<1)+5],tot[(N<<1)+5];

		inline void RadixSort(int S)

		{

			register int i;

			for(i=0;i<=S;++i) tot[i]=0;

			for(i=1;i<=n;++i) ++tot[rk[i]];

			for(i=1;i<=S;++i) tot[i]+=tot[i-1];

			for(i=n;i;--i) SA[tot[rk[pos[i]]]--]=pos[i];

		}

		inline void GetSA(char *s)

		{

			register int i,k,cnt=0,Size=122;

			for(n=strlen(s),i=1;i<=n;++i) rk[pos[i]=i]=s[i-1];

			for(RadixSort(Size),k=1;cnt<n;k<<=1)

			{

				for(Size=cnt,cnt=0,i=1;i<=k;++i) pos[++cnt]=n-k+i;

				for(i=1;i<=n;++i) SA[i]>k&&(pos[++cnt]=SA[i]-k);

				for(RadixSort(Size),i=1;i<=n;++i) pos[i]=rk[i];

				for(rk[SA[1]]=cnt=1,i=2;i<=n;++i) rk[SA[i]]=(pos[SA[i-1]]^pos[SA[i]]||pos[SA[i-1]+k]^pos[SA[i]+k])?++cnt:cnt;

			}

		}

		inline void GetHeight(char *s)

		{

			register int i,j,k=0;

			for(i=1;i<=n;++i) rk[SA[i]]=i;

			for(i=1;i<=n;++i)

			{

				if(!(rk[i]^1)) continue;

				k&&--k,j=SA[rk[i]-1];

				while(i+k<=n&&j+k<=n&&!(s[i+k-1]^s[j+k-1])) ++k;

				Height[rk[i]]=k;

			}

		}

	public:

		int SA[(N<<1)+5],Height[(N<<1)+5];

		inline void Init(char *s) {GetSA(s),GetHeight(s);}

}S;

int main()

{

	register int i,ans=0;

	scanf("%s",s),n=strlen(s),s[n]='%',scanf("%s",s+n+1),m=strlen(s+n+1);

	for(S.Init(s),i=1;i<=n+m;++i) if((S.SA[i]<n)^(S.SA[i-1]<n)) Gmax(ans,S.Height[i]);//如果相邻两个后缀的起始字符不在同一个字符串内，就更新答案

	return printf("%d",ans),0;

}

巴特西

【POJ2774】Long Long Message（后缀数组求Height数组）

关于后缀数组

大致思路

代码

最新文章

热门文章