POJ 3415 Common Substrings 题解《挑战程序设计竞赛》

POJ 3415 Common Substrings 

公共子串：统计A和B长度不小于K的公共子串个数。

4.7华丽地处理字符串 

后缀数组 

将A和B拼接后，累计分属两者的后缀对应的LCP-K+1即为答案，但穷举不是个好主意。

如果能快速求出任意两个后缀的最长公共前缀的话，利用类似尺取法的技巧就可以在线性时间统计一段区间了。

而任意两个后缀的最长公共前缀为该区间的LCP值的最小值。

在扫描一段LCA>=K的区域中，如果使用单调栈维护LCP，维护栈顶使LCP最小，就可以快速得到任意爬取区域的最长公共前缀。在“尺取法”爬取的过程中，更新出栈的元素对贡献值的影响，累积到答案中即可。

#include <iostream>
#include <string>
#include <algorithm>

const int MAX_L = 100000 + 1;
const int MAX_N = 2 * MAX_L + 1;
std::string S;
int n, k;
int sa[MAX_N + 1], lcp[MAX_N + 1];  // sa[i] := 字典序为i的后缀的起始下标；lcp[i] := S[sa[i]...]与S[sa[i+1]...]的最长公共前缀长度
int rank[MAX_N + 1], tmp[MAX_N + 1];

// 比较(rank[i], rank[i+k])和(rank[j], rank[j+k])
bool compare_sa(const int i, const int j)
{
    if (rank[i] != rank[j])
    {
        return rank[i] < rank[j];
    }
    return (i + k <= n ? rank[i + k] : -1) < (j + k <= n ? rank[j + k] : -1);
}

// 计算字符串S的后缀数组
void construct_sa()
{
    // 初始长度为1，rank直接取字符的编码
    for (int i = 0; i <= n; i++)
    {
        sa[i] = i;
        rank[i] = i < n ? S[i] : -1;
    }

    // 利用对长度为k的排序的结果对长度为2k的排序
    for (k = 1; k <= n; k <<= 1)
    {
        std::sort(sa, sa + n + 1, compare_sa);

        // 现在tmp中临时储存新计算的rank，再转存回rank中
        tmp[sa[0]] = 0;
        for (int i = 1; i <= n; i++)
        {
            tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
        }
        for (int i = 0; i <= n; i++)
        {
            rank[i] = tmp[i];
        }
    }
}

void construct_lcp()
{
    memset(lcp, 0, sizeof(lcp));
    for (int i = 0; i <= n; i++)
    {
        rank[sa[i]] = i;
    }
    int h = 0;
    lcp[0] = 0;
    for (int i = 0; i < n; i++)
    {
        int j = sa[rank[i] - 1];
        if (h > 0)
        {
            h--;
        }
        for (; i + h < n && j + h < n && S[i + h] == S[j + h]; h++);
        lcp[rank[i] - 1] = h;
    }
}

int stack[MAX_N][2];    // 0放lcp，1放个数
long long contribution, top;
using namespace std;

long long solve(int K, int l1, bool is_s1)
{
    long long ans = 0;
    for (int i = 0; i < n; i++)
    {
        if (lcp[i] < K)
        {
            top = contribution = 0;
        }
        else
        {// s1的后缀与s2的后缀的最长公共前缀大于k
            int size = 0;   // 满足条件的s1后缀个数
            if ((is_s1 && sa[i] < l1) || (!is_s1 && sa[i] > l1))
            {
                ++size;
                contribution += lcp[i] - K + 1;
            }
            while (top > 0 && lcp[i] <= stack[top - 1][0])
            {// 单调减栈，栈顶最小
                --top;
                contribution -= stack[top][1] * (stack[top][0] - lcp[i]); // 去掉出栈元素的贡献
                size += stack[top][1];
            }
            if (size)
            {
                stack[top][0] = lcp[i];
                stack[top][1] = size;
                ++top;
            }
            if ((is_s1 && sa[i + 1] > l1) || (!is_s1 && sa[i + 1] < l1)) // 与s2组合
            {
                ans += contribution;
            }
        }
    }
    return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int K;
    while (~scanf("%d", &K), K)
    {
        std::string s1, s2;
        std::cin >> s1 >> s2;
        int l1 = s1.length(), l2 = s2.length();
        S = s1 + '$' + s2;
        n = l1 + l2 + 1;
        construct_sa();
        construct_lcp();
        printf("%lld\n", solve(K, l1, true) + solve(K, l1, false));
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3415 Common Substrings 题解《挑战程序设计竞赛》