poj 2774 Long Long Message (最长公共字串，后缀数组模板题)

poj2774

题意：给出两个字符串，问最长的公共连续字串。

思路：后缀数组模板题。

具体可以参考两篇国集论文（09，04） topcoder中的讲解 codechef上的讲解 还有一篇讲 dc3算法的论文：SuffixArrays_dc3 这里不谈具体的后缀数组的学习内容，说说大概的学习过程。

首先要理解**后缀，后缀数组（sa[]），名次数组(rk[])，height数组，lcp **这些概念

先从定义入手，得到sa数组的n2logn的求法…

由于复杂度爆炸，所以有了两个算法来优化求sa的过程，一个是nlogn的倍增，还有一个是O(n)的dc3。。。

倍增的算法中用到了radix sort

上面这些，都是在说如何求sa,但是如果只有sa一个数组的话，就没有办法很好感受 后缀数组的power.

于是引入了height数组。

**定义 height[i]=suffix(sa[i-1])和 suffix(sa[i])的最长公** **共前缀,也就是排名相邻的两个后缀的最长公共前缀。那么对于 j 和 k,不妨设** **rank[j]

有很多问题都是基于height数组的，慢慢感受。

再说这道题：我们可以把两个字符串中间用一个特殊符号连接起来。

那么两个字符串的最长公共字串，就变成了求合并后的字符串的所有后缀的最长公共前缀。（原因是字符串的任何一个字串都可以看成是该字符串的某个后缀的前缀）

那么容易知道，该最长公共前缀的长度一定是某个height值（原因是，height[i]表示的是排名相邻的两个后缀的最长公共前缀的长度，如果不相邻，那么取的是他们排名之间所有height的最小值，只会越来越小。）

还需要注意的是，必须满足得到该height的两个后缀分别出现在原来的两个字符串中…

要怎么办到呢？ 其实很容易，由于sa[i]数组存放的是排名第i的后缀是后缀几(定义从第x个字符开始的后缀就是后缀x)

设初始第一个字符串的长度为len1,那么如果是第一个字符串的后缀，一定有sa[i]<len1,如果是第二个字符串的后缀，就一定有sa[i]>len1  (sa[i]==len1的是插入的特殊符号开始的后缀)

还有一些细节可以参考代码注释

UD20160730:改正了lrj书中的错误。。对于rk[i]==0的情况进行了特判。。不然会re…

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年07月30日 星期六 20时58分10秒
  4File Name :code/poj/2774.cpp
  5************************************************ */
  6#include <cstdio>
  7#include <cstring>
  8#include <iostream>
  9#include <algorithm>
 10#include <vector>
 11#include <queue>
 12#include <set>
 13#include <map>
 14#include <string>
 15#include <cmath>
 16#include <cstdlib>
 17#include <ctime>
 18#define fst first
 19#define sec second
 20#define lson l,m,rt<<1
 21#define rson m+1,r,rt<<1|1
 22#define ms(a,x) memset(a,x,sizeof(a))
 23typedef long long LL;
 24#define pi pair < int ,int >
 25#define MP make_pair
 26using namespace std;
 27const double eps = 1E-8;
 28const int dx4[4]={1,0,0,-1};
 29const int dy4[4]={0,-1,1,0};
 30const int inf = 0x3f3f3f3f;
 31const int N=2E5+7;
 32char s[N];
 33int sa[N],t[N],t2[N],cnt[N],n;
 34int c[N];
 35int w[N];
 36int rk[N],height[N];
 37int cmp( int *r,int a,int b,int l){ return r[a]==r[b]&&r[a+l]==r[b+l] ;};
 38void build_sa(int n,int m) //其实我觉得。。。sa怎么得到的不用管。。这部分讲道理不会变。。。反正知道能nlogn得到sa就对了2333
 39{
 40    int *x=t,*y=t2;
 41    // 基数排序（不是计数排序！） radix sort...
 42    for ( int i = 0 ; i < m ; i++) c[i] = 0 ; //ms(cnt,0);
 43    for ( int i = 0 ; i < n;  i++) c[x[i]=s[i]]++; //x[i]相当于保存了rank的相对大小，由于只是为了比较大小，所以没必要求出真实的rank值。
 44    for ( int i = 1 ; i < m ; i++) c[i]+=c[i-1];
 45    for ( int i = n-1 ; i >= 0 ;i--) sa[--c[x[i]]] =  i;
 46
 47
 48    for ( int k = 1 ; k <= n ; k<<=1)  //进行若干次基数排序，每次对长度为k的字符串排序
 49    {
 50	int p  = 0 ;
 51	for ( int i = n-k ; i < n ; i++)  y[p++] = i;  
 52	for ( int i = 0 ; i < n ; i++) if (sa[i]>=k) y[p++] = sa[i]-k; //y保存对第二关键字排序的结果，可以直接用上一次求得的sa算出。
 53	for ( int  i = 0 ; i < m  ;  i++) c[i] = 0;
 54	for ( int i = 0 ; i < n ; i++) c[x[y[i]]]++;
 55	for ( int i = 0 ; i < m ; i++) c[i]+=c[i-1];
 56	for ( int i = n-1 ; i >= 0 ; i--) sa[--c[x[y[i]]]] = y[i];
 57	swap(x,y);
 58	p = 1;
 59	x[sa[0]] = 0 ;
 60	for ( int i = 1 ; i < n ; i++)
 61	    x[sa[i]]= cmp(y,sa[i-1],sa[i],k)?p-1:p++;
 62	if (p>=n) break;
 63	m = p;
 64    }
 65}
 66void getHeight( int n)
 67{
 68    int k = 0 ;
 69    for ( int i = 0 ; i < n ; i++) rk[sa[i]] = i;
 70    height[0] = 0 ;
 71    for ( int i = 0 ; i < n ; i++) 
 72    {
 73	if (rk[i]==0) continue;
 74	if (k) k--;
 75	int j = sa[rk[i]-1];
 76	while (s[i+k]==s[j+k]) k++;
 77	height[rk[i]] = k;
 78    }
 79}
 80int getSuffix(char s[])
 81{
 82    int len = strlen(s);
 83    int up = 0 ;
 84    for ( int i =  0 ; i < len ; i++)
 85    {
 86	w[i] = s[i];
 87	up = max(up,w[i]);
 88    }
 89    w[len++] = 0 ;
 90    build_sa(len,up+1);
 91    getHeight(len);
 92    return len;
 93}
 94int main()
 95{
 96	#ifndef  ONLINE_JUDGE 
 97	freopen("code/in.txt","r",stdin);
 98  #endif
 99	string st1,st2,st;
100	cin>>st1>>st2;
101	int len1 = st1.length();
102	st = st1 + "$" + st2;
103	strcpy(s,st.c_str());
104	int len = getSuffix(s);
105//	cout<<"s:"<<s<<endl;
106//	for ( int i = 0 ; i < len ; i++) cout<<s[i]<<" "<<w[i]<<endl;
107//	for ( int i = 0 ; i < len ; i++) cout<<"sa[i]:"<<sa[i]<<endl;
108//	for ( int i = 0 ; i < len ; i++) cout<<"height[i]:"<<height[i]<<endl;
109
110	int ans = 0 ;
111     //  cout<<"len1:"<<len1<<endl;	
112	for ( int i = 2 ; i < len ; i++)
113	if (height[i]>ans)
114	{
115	    if (0<=sa[i-1]&&sa[i-1]<len1&&len1<sa[i]) ans = height[i];
116	    if (0<=sa[i]&&sa[i]<len1&&len1<sa[i-1]) ans = height[i];
117	}
118	printf("%d\n",ans);
119  #ifndef ONLINE_JUDGE  
120  fclose(stdin);
121  #endif
122    return 0;
123}