首页 > 编程语言 > 详细

HDU 5769 Substring (后缀数组)

时间:2019-09-16 19:03:56      阅读:74      评论:0      收藏:0      [点我收藏+]

题意:给定一个字符串和字符X,问有多少个包含X的不同子串

考虑后缀数组求不同子串的方法 : $ \sum_{i=1}^{n}(len+1-(sa[i]+height[i])) $
可以看出,对于每个i所贡献的所有子串都是以 sa[i] 开始,分别以 sa[i] + height[i] + 1 , sa[i] + height[i] + 2 ··· len 结尾的子串,所以只需要考虑在区间 [ sa[i] , sa[i] + height[i] ] 里有没有X,若有,则正常统计,若无,则需要找到 sa[i] + height[i] 后面第一次出现X的位置,从这里开始统计
所以只需要记录 sa[i] 之后X第一次出现的位置( 这里用 next[sa[i]] 表示 )
答案即为:\[ \sum_{i=1}^{n}(len+1-max(sa[i]+height[i],next[sa[i]])) \]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
int n;
int sa[maxn], x[maxn], c[maxn], y[maxn], height[maxn];
char s[maxn];
int near[maxn];
void SA()
{
    int m = 128;
    for (int i = 0; i <= m; i++)
        c[i] = 0;
    for (int i = 1; i <= n; i++)
        c[x[i] = s[i]]++;
    for (int i = 1; i <= m; i++)
        c[i] += c[i - 1];
    for (int i = n; i >= 1; i--)
        sa[c[x[i]]--] = i;

    for (int k = 1; k <= n; k <<= 1)
    {
        int p = 0;
        for (int i = 0; i <= m; i++)
            y[i] = 0;
        for (int i = n - k + 1; i <= n; i++)
            y[++p] = i;
        for (int i = 1; i <= n; i++)
            if (sa[i] > k)
                y[++p] = sa[i] - k;

        for (int i = 0; i <= m; i++)
            c[i] = 0;
        for (int i = 1; i <= n; i++)
            c[x[y[i]]]++;
        for (int i = 1; i <= m; i++)
            c[i] += c[i - 1];
        for (int i = n; i >= 1; i--)
            sa[c[x[y[i]]]--] = y[i];

        swap(x, y);
        x[sa[1]] = 1;
        p = 1;
        for (int i = 2; i <= n; ++i)
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? p : ++p;
        if (p >= n)
            break;
        m = p;
    }
}

void get_height()
{
    int k = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (x[i] == 1) continue;
        if (k) --k;
        int j = sa[x[i] - 1];
        while (j + k <= n && i + k <= n && s[i + k] == s[j + k]) ++k;
        height[x[i]] = k;
    }
}

int main()
{
    int t;
    scanf("%d", &t);
    for (int tt = 1; tt <= t; tt++)
    {
        getchar();
        char ch;
        scanf("%c%s", &ch, s + 1);
        n = strlen(s + 1);
        SA();get_height();
        memset(near, 0, sizeof(near));
        for (int i = n; i >= 1; i--)
        {
            if (s[i] == ch)
            {
                int pos = i;
                near[i] = i;
                i--;
                while (i >= 0 && s[i] != ch)
                {
                    near[i] = pos;
                    i--;
                }
                i++;
            }
        }
        ll ans = 0;
        for (int i = 1; i <= n; i++)
        {
            if (near[sa[i]] == 0)
                continue;
            ans += n - max(near[sa[i]], sa[i] + height[i]) + 1;
        }
        printf("Case #%d: %lld\n", tt, ans);
    }
    return 0;
}

HDU 5769 Substring (后缀数组)

原文:https://www.cnblogs.com/Zeronera/p/11528557.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!