POJ 3729 Facer’s string 题解《挑战程序设计竞赛》

POJ 3729 Facer’s string 

公共子串：

给出两个字符串A,B,求满足下列条件的C的个数:

1. C是A的子串

2. C也是B的子串

3. C加上其在A中的后继字符(若在最尾则加上空格字符)不能够在B中出现

4.7华丽地处理字符串 

后缀数组 

将A和B拼接后，lcp大于等于k的后缀中属于A的后缀一定满足条件。举个例子，A=123，B=1234，k=2，lcp和后缀如下：

0 : 
0 : $1234
3 : 123$1234
0 : 1234
2 : 23$1234
0 : 234
1 : 3$1234
0 : 34
0 : 4

为了满足条件3，只需将大于k的算一次就行。由于是后缀，所以不可能出现12$1234。统计lcp[i]>=k的连续区间内的A子串数。用>=k的数量减去>=k+1的数量得到刚好等于k的数量。

统计时利用如下性质即可：

#include<iostream>
#include <algorithm>

const int MAX_L = 50000 + 1;
const int MAX_N = 2 * MAX_L + 1;
int S[MAX_N];
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 N, M, K;
using namespace std;
// 能构成长度大于等于k的C的个数
int solve(int k)
{
    int ans = 0, A = 0, B = 0;
    for (int i = 0; i < n; i++)
    {// 统计lcp[i]>=k的连续区间内的A子串
        if (lcp[i] < k)
        {
            if (B > 0)
                ans += A;
            A = 0;
            B = 0;
        }
        if (sa[i + 1] < N)
            A++;
        else
            B++;
    }
    return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("err.txt", "w", stderr);
#endif
    while (~scanf("%d%d%d", &N, &M, &K))
    {
        n = N + M + 1;
        for (int i = 0; i < N; i++)
        {
            scanf("%d", &S[i]);
            S[i]++;
        }
        S[N] = 10000 + 8;
        for (int i = N + 1; i < n; i++)
        {
            scanf("%d", &S[i]);
            S[i]++;
        }
        S[n] = 0;
        construct_sa();
        construct_lcp();
        printf("%d\n", solve(K) - solve(K + 1));
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stderr);
#endif
    return 0;
}

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