最长公共子串问题(LCS)

  • 定义:给定字符串长度最大的公有子串,使用后缀数组可达到$O(nLlogL)$,其中$n为字符串个数$,$L$为每个字符串长度
  • 等效于求两个后缀的公共前缀(LCP)

后缀数组相关概念

  • SA[i]:排名为i的后缀的位置(第i是谁)
  • Rank[i]:第i个后缀suffix(i)的排名
  • 对于已经排好序的字符串,任意两个的公共最长前缀为$LCP(s[i], s[j]) = min \{ LCP(s[k], s[k + 1]) , i \le k < j\}$,LCP转化成区间最小值RMQ问题
  • height[i]:定义height[i] = LCP(SA[i - 1], SA[i]),则$LCP(s[i], s[j]) = min \{ height[k] , i \le k < j\}$

后缀数组具体求法

  • 使用基于倍增的算法,通过所有长为x的前缀的顺序求出长为2x的前缀顺序——基数排序
    经过$log(s.length)$完成对所有后缀的排序
  • height数组
    h[i] = height[rank[i]],则suffix(i - 1)与其排序中的前一名的公共前缀至少为h[i - 1] - 1,可依据此在$O(n)$求得h[i]h[i]不需要单独保存,直接写入height[i]即可

后缀数组的实现

void init()
{
    scanf("%s\n", s + 1);
    N = strlen(s + 1);
    s[N] = 'z' + 1;
    scanf("%s", s + N + 1);
    M = strlen(s + N + 1);
    L = N + M + 1;
}

int rank[MAXN * 2], sa[MAXN], h[MAXN], text[MAXN];
char s[MAXN];

void getSA()
{
    for(int i = 1; i <= L; i++)
        text[i] = s[i] - 'a' + 1;
    static int cnt[MAXN], q[MAXN], t[MAXN];
    memset(cnt, 0, sizeof(cnt));

    for(int i = 1; i <= L; i++)
        cnt[text[i]]++;
    for(int i = 1; i <= 30; i++)
        cnt[i] += cnt[i - 1];
    for(int i = 1; i <= L; i++)
        rank[i] = cnt[text[i]];

    for(int len = 1; len < L; len *= 2)
    {
        //先对第二关键字排序
        memset(cnt, 0, sizeof(cnt));
        for(int i = 1; i <= L; i++)
            cnt[rank[i + len]]++;
        for(int i = 1; i <= L; i++)
            cnt[i] += cnt[i - 1];
        for(int i = 1; i <= L; i++)
            q[cnt[rank[i + len]]--] = i;

        memset(cnt, 0, sizeof(cnt));
        for(int i = 1; i <= L; i++)
            cnt[rank[i]]++;
        for(int i = 1; i <= L; i++)
            cnt[i] += cnt[i - 1];
        for(int i = L; i >= 1; i--)
            t[cnt[rank[q[i]]]--] = q[i];

        q[1] = 1;
        for(int i = 2; i <= L; i++)
            q[i] = q[i - 1] + \
        (rank[t[i]] != rank[t[i - 1]] || rank[t[i] + len] != rank[t[i - 1] + len]);
        for (int i = 1; i <= L; i++) 
            rank[t[i]] = q[i];
    }
}
void buildH()
{
    for(int i = 1; i <= L; i++)
        sa[rank[i]] = i;
    for(int i = 1, len = 0; i <= L; i++)
    {
        if(len)
            len--;
        while(s[i + len] == s[sa[rank[i] - 1] + len])
            len++;
        h[rank[i]] = len;
    }
}