Ural 1517. Freedom of Choice 后缀数组

Ural1517 所谓后缀数组，实际上准确的说，应该是排序后缀数组。

一个长度为N的字符串，显然有N个后缀，将他们放入一个数组中并按字典序排序就是后缀数组的任务。

这个数组有很好的性质，使得我们运行一些算法时可以大幅度的优化。

本题就是后缀数组的一个主要应用，快速求得后缀S（i）和S（j）的最长公共前缀LCP。

**由字典序的性质可知 S（i）和S（j）的LCP长度就是 h[sa[i]+1],h[sa[i]+2].... h[sa[j]]中的最小值，证明显然。

**而如何计算h数组呢？有一个性质 h[rank[i]]>=h[rank[i-1]]-1. 由两两对应关系可以证明（同时去掉首字符）。

代码如下后缀数组并不复杂

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<string.h>

#include<cmath>

#include<vector>

#include<algorithm>

#include<queue>

using namespace std;

const int MAXN=200000+100;

void radix(int *str,int *a,int *b,int n,int m)

{

 static int count[MAXN];

 memset(count,0,sizeof(count));

 for(int i=0;i<n;++i)++count[str[a[i]]];

 for(int i=1;i<=m;++i)count[i]+=count[i-1];

 for(int i=n-1;i>=0;--i)b[--count[str[a[i]]]]=a[i];

}

void sorted_suffix_array(int *str,int *sa,int n,int m)

{

 static int rank[MAXN],a[MAXN],b[MAXN];

 for(int i=0;i<n;++i)rank[i]=i;

 radix(str,rank,sa,n,m);

 rank[sa[0]]=0;

 for(int i=1;i<n;++i)rank[sa[i]]=rank[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]);

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

 	{

 	 for(int j=0;j<n;++j)

 	 	{

 	 	 a[j]=rank[j]+1;

 	 	 b[j]=j+(1<<i)>=n? 0:rank[j+(1<<i)]+1;

 	 	 sa[j]=j;

		}

	 radix(b,sa,rank,n,n);

	 radix(a,rank,sa,n,n);

	 rank[sa[0]]=0;

	 for(int j=1;j<n;++j)

	 	{

	 	 rank[sa[j]]=rank[sa[j-1]]+(a[sa[j-1]]!=a[sa[j]]||b[sa[j-1]]!=b[sa[j]]);

		}

	}

}

void calc_height(int *str,int *sa,int *h,int n)

{

 static int Rank[MAXN];

 int k=0;

 h[0]=0;

 for(int i=0;i<n;++i)Rank[sa[i]]=i;

 for(int i=0;i<n;++i)

 	{

 	 k= k==0?0:k-1;

 	 if(Rank[i]!=0)

 	   while(str[i+k]==str[sa[Rank[i]-1]+k])++k;

 	 h[Rank[i]]=k;

	}

}

int work(string a,string b)

{

 static int s[MAXN],sa[MAXN],h[MAXN];

 string str;

 str=a+"#"+b;

 copy(str.begin(),str.end(),s);

 sorted_suffix_array(s,sa,str.length(),str.length()+256);

 calc_height(s,sa,h,str.length());

 int ans=0,pos;

 for(int i=1;i<str.length();++i)

 	{

 	 if(h[i]>ans&&(sa[i-1]<a.length())!=(sa[i]<a.length()))

 	 	{

 	 	 ans=h[i];

 	 	 pos=sa[i];

		}

	}

 cout<<str.substr(pos,ans)<<endl;

}

int main()

{freopen("t.txt","r",stdin);

 ios::sync_with_stdio(false);

 int n;

 cin>>n;

 string a,b;

 cin>>a>>b;

 work(a,b);

 return 0;

}

巴特西

Ural 1517. Freedom of Choice 后缀数组

最新文章

热门文章