一些碎碎念

在学习了一个星期的后缀树组后,终于搞懂了。一开始看那个论文各种雾啊,明明讲的是rank数组倍增,代码写的却是sa,唉!
在为数不多能1A的题中,POJ2774算一个吧。

解题思路

将两个字符串连接起来,然后求height数组,然后取height数组中的最大值,并且其排名相同的两个后缀的开头分别属于不同的串,即判断一个开头小于strlen(s1),另一个大于即可。你可能会有疑惑,因为可能答案的那两个串在排序后可能不相邻,但事实是相邻的,因为若他们之间还有一些后缀的话,那答案就不会是开始那两个了,而是他们中间某一个。这点由后缀数组的性质很容易想明白。如你所见,我也不知道如何完整地去证明,如果你能证明,请在评论处发表。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN 250000
using namespace std;
char s[MAXN];
char s2[100050];
int len1, len2, n;
int wa[MAXN], wb[MAXN], c[128];
int sa[MAXN], rank[MAXN], height[MAXN];
int maxx; //即最终答案

void Build_sa(int m)
{
    int i, *x=wa, *y=wb;
    for(i=0; i<m; i++) c[i] = 0;
    for(i=0; i<n; i++) c[x[i] = s[i]-'a']++;
    for(i=1; i<m; i++) c[i] += c[i-1];
    for(i=n-1; i>=0; i--) sa[--c[x[i]]] = i;
    for(int k=1; k<=n; k<<=1)
    {
        int p = 0;
        for(i=n-1; i>=n-k; i--) y[p++] = i;
        for(i=0; i<n; i++) if(sa[i]>=k) y[p++] = sa[i]-k;
        for(i=0; i<m; i++) c[i] = 0;
        for(i=0; i<n; i++) c[x[y[i]]]++;
        for(i=1; i<m; i++) c[i] += c[i-1];
        for(i=n-1; i>=0; i--) sa[--c[x[y[i]]]] = y[i];
        swap(x,y);
        p = 1; x[sa[0]] = 0;
        for(i=1; i<n; i++)
            x[sa[i]] = (y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+k]==y[sa[i]+k])?p-1:p++;
        if(p >= n) break;
        m = p;
    }
}

void Build_height()
{
    int i, j, k = 0;
    for(i=0; i<n; i++)
    if(rank[i] > 0)
    {
        if(k) k--;
        j = sa[rank[i]-1];
        while(s[i+k]==s[j+k]) k++;
        height[rank[i]] = k;
    }
}

int main()
{
    scanf("%s", s);
    len1 = strlen(s);
    scanf("%s", s2);
    len2 = strlen(s2);
    strcat(s, s2);
    n = len1 + len2;
    Build_sa(30);
    for(int i=0; i<n; i++) rank[sa[i]] = i;
    Build_height();
    maxx = -1;
    for(int i=1; i<n; i++)
    if((sa[i-1]<=len1 && sa[i]>=len1) || (sa[i-1]>=len1 && sa[i]<=len1)) //判断是否分属两个串
        if(height[i] > maxx) maxx = height[i];
    printf("%d\n", maxx);
    return 0;
}