POJ2774 Long Long Message

2014.12.08 20:54 Mon| 1 visits oi_2015| 2015_刷题日常| Text

poj不支持#include <bits/stdc++.h>真是坑啊……

Solution

题意即给出两个字符串,求出两个字符串最长公共子串长度。

将两字符串以分隔符相隔后求出后缀数组。沿sa数组扫一遍,直接判断若名次相邻的两个后缀串同属于两个不同字符串,便可更新答案。

注意判断时使用if((sa[i]<len&&sa[i-1]>len)||(sa[i]>len&&sa[i-1]<len))。若用乘积的符号判断需注意可能会爆long long

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 200500

char str[N];
int len,n,c[N],x[N],y[N],sa[N],rank[N],height[N];

inline bool same(int a,int b,int k)
{
    return y[a]==y[b] && ((a+k>=n&&b+k>=n)||(a+k<n&&b+k<n&&y[a+k]==y[b+k]));
}

void get_sa(int m=256)
{
    for(int i=0;i<n;i++) c[x[i]=str[i]]++;
    for(int i=1;i<m;i++) c[i]+=c[i-1];
    for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
    for(int k=1;k<n;k<<=1)
    {
        int p=0;
        for(int i=n-k;i<n;i++) y[p++]=i;
        for(int i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
        memset(c,0,m*sizeof(int));
        for(int i=0;i<n;i++) c[x[y[i]]]++;
        for(int i=1;i<m;i++) c[i]+=c[i-1];
        for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
        for(int i=0;i<n;i++) y[i]=x[i];
        m=0; x[sa[0]]=0;
        for(int i=1;i<n;i++)
            x[sa[i]]=same(sa[i-1],sa[i],k)?m:++m;
        if(++m==n) break;
    }
}

void get_height()
{
    for(int i=0;i<n;i++) rank[sa[i]]=i;
    for(int i=0,j,k=0;i<n;height[rank[i++]]=k)
        if(rank[i]) for(k?k--:0,j=sa[rank[i]-1];str[i+k]==str[j+k];k++);
}

int main()
{
    scanf("%s",str);
    len=strlen(str);
    str[len]='z'+1;
    scanf("%s",str+len+1);
    n=strlen(str);
    get_sa(256);
    get_height();
    int ans=0;
    for(int i=1;i<n;i++)
        if((long long)(sa[i]-len)*(sa[i-1]-len)<0)
            ans=max(ans,height[i]);
    cout<<ans<<endl;
    return 0;
}