poj 2774(后缀数组)

发表于 | 分类于 | | + s

poj 2774

给出两个字符串，求这两个字符串的公共子串。

我们可以连接两个字符串，中间插入$\$$，然后构造后缀数组，用$height$数组解决。

以abbbc和bbc为例。

因为后缀数组是字典序排的，所以排名最近的两个后缀拥有的最大公共前缀一定比不相邻的长。所以，由图可知，只要后缀$i$的位置在串1的范围，后缀$i-1$在串2的范围(反过来亦可)，那么就可以用$height[i]$更新$ans$的答案

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define FN2 "poj2774" 
using namespace std;

const int MAXN = 100000 + 5;

char s1[MAXN], s2[MAXN];
int l1, l2, n, m, a[MAXN*2+100], SA[MAXN*2+100], rk[MAXN*2+100], tp[MAXN*2+100], height[MAXN*2+100], tax[MAXN*2+100];

bool cmp(int *f, int i, int k) {return f[SA[i]]==f[SA[i-1]]&&f[SA[i]+k]==f[SA[i-1]+k];}
void build() {
    for (int i=0;i<m;i++) tax[i] = 0;
    for (int i=0;i<n;i++) tax[rk[i]=a[i]]++;
    for (int i=1;i<m;i++) tax[i] += tax[i-1];
    for (int i=n-1;i>=0;i--) SA[--tax[rk[i]]] = i;
    int p;
    for (int k=1;k<=n;k*=2) {
        p = 0;
        for (int i=n-k;i<n;i++) tp[p++] = i;
        for (int i=0;i<n;i++) if (SA[i]>=k) tp[p++] = SA[i] - k;

        for (int i=0;i<m;i++) tax[i] = 0;
        for (int i=0;i<n;i++) tax[rk[tp[i]]]++;
        for (int i=1;i<m;i++) tax[i] += tax[i-1];
        for (int i=n-1;i>=0;i--) SA[--tax[rk[tp[i]]]] = tp[i];

        swap(rk, tp), rk[SA[0]] = 0, p = 0;
        for (int i=1;i<n;i++) rk[SA[i]] = cmp(tp, i, k) ? p : ++p;
        if (++p>=n) break;
        m = p;
    }
}
void getH() {
    int k = 0;
    for (int i=0;i<n;i++) {
        if (k) k--;
        int j = SA[rk[i]-1];
        while (a[i+k]==a[j+k]) k++;
        height[rk[i]] = k;
    }
}
void init() {
    scanf("%s", s2);
    l1 = strlen(s1), l2 = strlen(s2);
    n = l1 + l2 + 2, m = 128;
    for (int i=0;i<l1;i++) a[i] = s1[i];
    a[l1] = '$', a[n-1] = 0;
    for (int i=0;i<l2;i++) a[l1+1+i] = s2[i];
}
void solve() {
    build(), getH();
    int ans = 0;
    for (int i=2;i<n;i++) if (height[i]>ans) {
        if ((0<=SA[i]&&SA[i]<l1&&SA[i-1]>l1) || (0<=SA[i-1]&&SA[i-1]<l1&&SA[i]>l1)) ans = height[i];
        //i在第一个字符串内，i-1在第二个字符串内
        //或者i-1在第一个字符串内，i在第二个字符串内
    }
    printf("%d\n", ans);
}
int main() {
    #ifndef ONLINE_JUDGE
    freopen(FN2".in","r",stdin);freopen("1.out","w",stdout);
    #endif
    while(scanf("%s", s1)==1) init(), solve();
    return 0;
}
------ 本文结束 ------