放牧代码和思想
专注自然语言处理、机器学习算法
    愛しさ 優しさ すべて投げ出してもいい

AOJ 2292 Common Palindromes 题解《挑战程序设计竞赛》

目录

Common Palindromes.png

AOJ 2292 Common Palindromes 

公共回文子串:求两个串的公共回文子串个数。

4.7华丽地处理字符串 

后缀数组 

拼接后先预处理出后缀数组、高度数组和回文半径数组。其中,每个位置的回文半径用Manacher算法线性时间求出。

定义a[plen]为半径=plen的公共回文子串的个数,下面看怎么逐步求a[plen]。按照后缀字典序遍历公共子串,维护目前遇到过的包含该公共子串的回文子串。

假设回文串长度为奇数,比如例题的遍历顺序如下(后缀|公共子串|回文串):

$CPCPC |  | CPC$CPC
C |  | C
C$CPCPC | C | C
CPC | C | CPCPC
CPC$CPCPC | CPC | C
CPCPC | CPC | C
ICPC$CPCPC |  | I
PC |  | CPC
PC$CPCPC | PC | CPC
PCPC | PC | CPC

在每遇到一个长clen公共子串c的过程中,都遍历长度plen大于clen的公共回文子串p,将p的个数加到区间[clen, plen]中的每一个元素上去。因为每出现一次长plen的公共回文子串p,都代表出现了一次plen-1,plen-2, … clen的公共回文子串,示意图如下:

Common Palindromes.png

涉及到区域批量修改,所以要用BIT

对每个位置k,都将区域和a[1,plen]累积到答案上即可。

#include <iostream>
#include <string>
#include <cstring>
#include <map>
#include <algorithm>

using namespace std;
typedef long long LL;

struct SA
{
    static const int N = 200000; // len+1<=N
    int a[N], lcp[N];

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

    void build(const char *t, int n)
    {
        // suffix array
        static int g[N], b[N];
        for (int i = 0; i < n + 1; ++i)
        {
            a[i] = i, g[i] = t[i];
        }
        b[0] = b[n] = 0;
        sort(a, a + n + 1, SAComp(0, g));
        for (int h = 1; b[n] != n; h *= 2)
        {
            SAComp comp(h, g);
            sort(a, a + n + 1, comp);
            for (int i = 0; i < n; ++i)
            {
                b[i + 1] = b[i] + comp(a[i], a[i + 1]);
            }
            for (int i = 0; i < n + 1; ++i)
            {
                g[a[i]] = b[i];
            }
        }
        // longest common prefix (you can omit here)
        for (int i = 0; i < n + 1; ++i)
        {
            b[a[i]] = i;
        }
        int h = 0;
        for (int i = 0; i < n; ++i)
        {
            const int j = a[b[i] - 1];
            while (j + h < n && i + h < n && t[j + h] == t[i + h])
                h++;
            lcp[b[i]] = h;
            if (h)
                h--;
        }
        lcp[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;

struct Manacher
{
    static const int N = 200000 * 2; // len*2
    int rad[N];

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

    void build(const char *t, int n)
    {
        int k;
        for (int i = 0, j = 0; i < 2 * n; i += k, j = max(j - k, 0))
        {
            while (i - j >= 0 && i + j + 1 < 2 * n && t[(i - j) / 2] == t[(i + j + 1) / 2])
                j++;
            rad[i] = j;
            for (k = 1; i - k >= 0 && rad[i] - k >= 0 && rad[i - k] != rad[i] - k; k++)
            {
                rad[i + k] = min(rad[i - k], rad[i] - k);
            }
        }
    }
} mana;

struct BIT
{
    static const int N = 80000;
    LL x[N];

    void init()
    { memset(x, 0, sizeof(x)); }

    void add(int k, LL a)
    {
        for (; k < N; k |= k + 1)
            x[k] += a;
    }

    LL sum(int k)
    {
        LL s = 0;
        for (; k >= 0; k = (k & (k + 1)) - 1)
            s += x[k];
        return s;
    }

    LL rsum(int i, int j)
    { return i == 0 ? sum(j) : sum(j) - sum(i - 1); }

    LL esum(int i)
    { return rsum(i, N - 1); }
} sum[2], cnt[2];

int of[200000];

int main()
{
    string S, T;
    cin >> S >> T;
    const string F(S + '$' + T);
    sa.build(F);
    mana.build(F);
    for (int i = 0; i < F.size() + 1; ++i)
    {
        of[i] = sa.a[i] > (int) S.size();
    }

    LL ans = 0;
    for (int odd = 0; odd < 2; ++odd)// 回文长度是否为奇数
    {
        for (int i = 0; i < 2; ++i)
            sum[i].init(), cnt[i].init();
        map<int, int> palindrome[2];// AB各自的回文子串半径plen的个数
        for (int k = 1; k < (int) F.size() + 1; k++)
        {
            const int clen = sa.lcp[k];// 公共子串的长度
            for (int i = 0; i < 2; ++i)
            {
                map<int, int>::iterator it = palindrome[i].lower_bound(clen + 1);
                while (it != palindrome[i].end())// 遍历半径大于公共子串clen的回文子串
                {//维护Binary Indexed Tree
                    const int plen = it->first, p = it->second;// 回文子串长度及个数
                    sum[i].add(plen, -(LL) plen * p);//在[clen,plen]区间同时加上p
                    cnt[i].add(plen, -p);
                    sum[i].add(clen, (LL) clen * p);
                    cnt[i].add(clen, p);
                    palindrome[i][clen] += p;
                    palindrome[i].erase(it++);
                }
            }// 在sa[k]位置的回文半径
            const int plen = odd ? mana.rad[sa.a[k] * 2] / 2 + 1 : sa.a[k] ? mana.rad[sa.a[k] * 2 - 1] / 2 : 0;
            ans += sum[1 - of[k]].sum(plen) + (LL) plen * cnt[1 - of[k]].esum(plen + 1);//前plen项之和
            sum[of[k]].add(plen, plen); // a[plen] += 1
            cnt[of[k]].add(plen, 1);
            palindrome[of[k]][plen]++;
        }
    }
    cout << ans << endl;
    return 0;
}

hankcs.com 2017-02-10 下午10.43.35.png

Reference

http://d.hatena.ne.jp/kohyatoh/

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

评论 欢迎留言

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

我的作品

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