POJ-2774-Long Long Message(后缀数组-最长公共子串)

题意：

给定两个字符串 A 和 B,求最长公共子串。

分析：

字符串的任何一个子串都是这个字符串的某个后缀的前缀。

求 A 和 B 的最长公共子串等价于求 A 的后缀和 B 的后缀的最长公共前缀的最大值。如果枚举 A和 B 的所有的后缀,那么这样做显然效率低下。

由于要计算 A 的后缀和 B 的后缀的最长公共前缀,所以先将第二个字符串写在第一个字符串后面,中间用一个没有出现过的字符隔开,再求这个新的字符串的后缀数组。

观察一下,看看能不能从这个新的字符串的后缀数组中找到一些规律。以 A=“aaaba”,B=“abaa”为

POJ-2774-Long Long Message(后缀数组-最长公共子串)

那么是不是所有的 height 值中的最大值就是答案呢?不一定!有可能这两个后缀是在同一个字符串中的 , 所以实际上只有当 suffix(sa[i-1]) 和suffix(sa[i])不是同一个字符串中的两个后缀时,height[i]才是满足条件的。

而这其中的最大值就是答案。

// File Name: 2774.cpp
// Author: Zlbing
// Created Time: 2013年09月07日 星期六 14时55分24秒

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
#define REP(i,r,n) for(int i=r;i<=n;i++)
#define RREP(i,n,r) for(int i=n;i>=r;i--)
//rank从0开始
//sa从1开始,因为最后一个字符(最小的)排在第0位
//height从2开始,因为表示的是sa[i-1]和sa[i]
const int MAXN=220000;
int rank[MAXN],sa[MAXN],X[MAXN],Y[MAXN],height[MAXN];
char s[MAXN];
int buc[MAXN];
void calheight(int n) {
    int i , j , k = 0;
    for(i = 1 ; i <= n ; i++) rank[sa[i]] = i;
    for(i = 0 ; i < n ; height[rank[i++]] = k)
        for(k?k--:0 , j = sa[rank[i]-1] ; s[i+k] == s[j+k] ; k++);
}
bool cmp(int *r,int a,int b,int l) {
    return (r[a] == r[b] && r[a+l] == r[b+l]);
}
void suffix(int n,int m = 128) {
    int i , l , p , *x = X , *y = Y;
    for(i = 0 ; i < m ; i ++) buc[i] = 0;
    for(i = 0 ; i < n ; i ++) buc[ x[i] = s[i]  ] ++;
    for(i = 1 ; i < m ; i ++) buc[i] += buc[i-1];
    for(i = n - 1; i >= 0 ; i --) sa[ --buc[ x[i] ]] = i;
    for(l = 1,p = 1 ; p < n ; m = p , l *= 2) {
        p = 0;
        for(i = n-l ; i < n ; i ++) y[p++] = i;
        for(i = 0 ; i < n ; i ++) if(sa[i] >= l) y[p++] = sa[i] - l;
        for(i = 0 ; i < m ; i ++) buc[i] = 0;
        for(i = 0 ; i < n ; i ++) buc[ x[y[i]] ] ++;
        for(i = 1 ; i < m ; i ++) buc[i] += buc[i-1];
        for(i = n - 1; i >= 0 ; i --) sa[ --buc[ x[y[i]] ] ] = y[i];
        for(swap(x,y) , x[sa[0]] = 0 , i = 1 , p = 1 ; i < n ; i ++)
            x[ sa[i] ] = cmp(y,sa[i-1],sa[i],l) ? p-1 : p++;
    }
    calheight(n-1);//后缀数组关键是求出height,所以求sa的时候顺便把rank和height求出来
}
//当需要反复询问两个后缀的最长公共前缀时用到RMAXNQ
int Log[MAXN];
int best[20][MAXN];
void initRMQ(int n) {//初始化RMQ
    for(int i = 1; i <= n ; i ++) best[0][i] = height[i];
    for(int i = 1; i <= Log[n] ; i ++) {
        int limit = n - (1<<i) + 1;
        for(int j = 1; j <= limit ; j ++) {
            best[i][j] = min(best[i-1][j] , best[i-1][j+(1<<i>>1)]);
        }
    }
}
int lcp(int a,int b) {//询问a,b后缀的最长公共前缀
    a = rank[a];    b = rank[b];
    if(a > b) swap(a,b);
    a ++;
    int t = Log[b - a + 1];
    return min(best[t][a] , best[t][b - (1<<t) + 1]);
}
int main() {
    //预处理每个数字的Log值,常数优化,用于RMQ
    Log[0] = -1;
    for(int i = 1; i < MAXN ; i ++) {
        Log[i] = (i&(i-1)) ? Log[i-1] : Log[i-1] + 1 ;
    }
    //*******************************************
    //    n为数组长度,下标0开始
    //    将初始数据,保存在s里,并且保证每个数字都比0大
    //    m = max{ s[i] } + 1
    //    一般情况下大多是字符操作,所以128足够了
    //*******************************************
    char ch[MAXN];
    while(~scanf("%s",s))
    {
        scanf("%s",ch);
        int len1=strlen(s);
        int len2=strlen(ch);
        s[len1]=1;
        for(int i=len1+1;i<len1+len2+1;i++)
            s[i]=ch[i-len1-1];
        int n=len1+len2+2;
        s[n]=0;
        suffix(n);
        initRMQ(n);
        int ans=0;
        for(int i=3;i<=n;i++)
        {
            if((sa[i-1]<len1&&sa[i]>len1)||(sa[i-1]>len1&&sa[i]<len1))
            {
                ans=max(ans,height[i]);
            }
        }
        printf("%d
",ans);
    }

    return 0;
}

POJ-2774-Long Long Message(后缀数组-最长公共子串)

相关推荐