放牧代码和思想
专注自然语言处理、机器学习算法
    This thing called love. Know I would've. Thrown it all away. Wouldn't hesitate.

Codeforces 123D String 题解《挑战程序设计竞赛》

目录

挑战程序设计竞赛第二版.jpg

Codeforces 123D String 

子串函数和:求字符串的所有子串出现次数n代入n(n+1)/2之和。

4.7华丽地处理字符串 

后缀数组 

题目有些绕,直白地讲就是枚举所有不同的子串,求出现次数,代入该表达式求和。枚举子串的通用做法是,高度数组连续一段不小于h的区间长度代表长h的子串的出现次数。将高度数组视作x轴上宽度为1,高度为height[i]的矩形序列的话,出现次数就是求高度大于h的最宽矩形。

这种问题的求法也有定式,就是类似书上栈的那节用单调栈的做法。定义一个公共前缀长度height的非严格递增栈。

每次插入height[i]时弹出的那些元素end与i共同构成“最宽矩形”的始末区间,所以矩形宽度为i-end。这些矩形的高度就对应着一个子串。

进一步,若子串A包含子串B,则说明有A.length-B.length个长B.length的子串出现次数都是i-end。如果某后缀的长度比当前height大,后缀的height也比当前height大,该公共前缀就包含当前公共前缀,就会发生这种情况了。

子串个数乘以f(子串出现次数),累加到答案上即可。

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>

using namespace std;

const int MAX_N = 100100;

struct SuffixArray
{
    int sa[MAX_N], height[MAX_N];

    void build(const string &s)
    { build(s.c_str(), s.size()); }

    void build(const char *t, int n)
    {
        // suffix array
        static int g[MAX_N], b[MAX_N];
        for (int i = 0; i < n + 1; ++i)
        {
            sa[i] = i, g[i] = t[i];
        }
        b[0] = b[n] = 0;
        sort(sa, sa + n + 1, SAComp(0, g));
        for (int h = 1; b[n] != n; h *= 2)
        {
            SAComp comp(h, g);
            sort(sa, sa + n + 1, comp);
            for (int i = 0; i < n; ++i)
            {
                b[i + 1] = b[i] + comp(sa[i], sa[i + 1]);
            }
            for (int i = 0; i < n + 1; ++i)
            {
                g[sa[i]] = b[i];
            }
        }
        // longest common prefix (you can omit here)
        for (int i = 0; i < n + 1; ++i)
        {
            b[sa[i]] = i;
        }
        int h = 0;
        for (int i = 0; i < n; ++i)
        {
            const int j = sa[b[i] - 1];
            while (j + h < n && i + h < n && t[j + h] == t[i + h])
                h++;
            height[b[i]] = h;
            if (h)
                h--;
        }
        height[0] = -1;
    }

    struct SAComp
    {
        const int h, *g;

        SAComp(int h, int *g) : h(h), g(g)
        {}

        bool operator()(int l, int r)
        {
            return g[l] != g[r] ? g[l] < g[r] : g[l + h] < g[r + h];
        }
    };
} sa;

char buf[MAX_N];

long long cnt(long long n)
{
    return n * (n + 1) / 2;
}

int main()
{
#ifndef  ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("err.txt", "w", stderr);
#endif
    int n;
    long long ans;
    vector<pair<pair<int, int>, int>> v;//单调栈

    scanf("%s", buf);
    n = (int) strlen(buf);
    sa.build(buf, n);
    sa.height[n + 1] = 0;
    sa.sa[n + 1] = n;
    ans = 0;
    for (int i = 1; i <= n + 1; ++i)
    {
        while (!v.empty() && v.back().first.second > sa.height[i])
        {
            auto &end = v.back();// 某子串出现i-end.second次
            if (end.first.first < sa.height[i])//队尾公共前缀长度小于当前公共前缀长度
            {// 有(end.公共前缀长度减去当前公共前缀长度)种子串
                ans += (end.first.second - sa.height[i]) * cnt(i - end.second);
                end.first.second = sa.height[i];//维护非严格单调增栈
            }
            else
            {
                ans += (end.first.second - end.first.first) * cnt(i - end.second);
                v.pop_back();//维护非严格单调增栈
            }
        }
        v.push_back({{sa.height[i], n - sa.sa[i]}, i});
    }
    printf("%lld\n", ans);
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stderr);
#endif
    return 0;
}

hankcs.com 2017-02-11 下午9.49.20.png

Reference

译者的代码:https://searchcode.com/codesearch/view/30101319/

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » Codeforces 123D String 题解《挑战程序设计竞赛》

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的作品

HanLP自然语言处理包《自然语言处理入门》