Link

http://acm.timus.ru/problem.aspx?space=1&num=2060

Problem

Your task is to calculate number of triplets (i, j, k) such that ij < k and s[i..j] is a palindrome and s[j+1 .. k] is a palindrome.

Mean

给一个最长为300000的字符串s,问有多少个三元组(i,j,k),使得s[i:j]和s[j+1:k]均为回文串。

Analysis

这是URAL的一场回文串专场的最简单的一道题。

首先用Manacher处理出每个中心点到两边的最长回文串的长度,这样就可以对这个长度区间内同时+1,这样就求出了以当前点结尾、开头的回文串个数。最后枚举j和j+1的中心(Manacher中插入的’#’)计数即可。

注意Manacher对于回文串中插入的’#’的处理。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 6 * 102400;
char s[maxn];
int len;
vector<int> ans;

struct BIT {
    int dat[maxn];
    void clear() {
        memset(dat, 0, sizeof(dat));
    }
    int query(int pos) {
        int s = 0;
        for(int i = pos; i < maxn; i += (i&-i))
            s += dat[i];
        return s;
    }
    void addRange(int l, int r, int d) {
        for(int i = r; i > 0; i -= (i&-i))
            dat[i] += d;
        for(int i = l-1; i > 0; i -= (i&-i))
            dat[i] -= d;
    }
}bitL, bitR;

void Manacher(const string & str, vector<int> &res) {
    string t = "$#";
    for(auto i : str)
        t.push_back(i), t.push_back('#');
    res.resize(t.size(), 0);
    int mx = 0, id = 0;
    for(int i = 0; i < t.size(); ++i) {
        res[i] = mx > i ? min(res[2*id-i], mx-i) : 1;
        while(t[i+res[i]] == t[i-res[i]]) ++res[i];
        if(i + res[i] > mx) {
            mx = i + res[i];
            id = i;
        }
    }
//    for(int i = 0; i < res.size(); ++i) {
//        printf("%d : %c : %d\n", i, t[i], res[i]);
//    }
    bitL.clear(), bitR.clear();
    for(int i = 1; i < res.size(); ++i) {
        bitL.addRange(i - res[i] + 1, i, 1);
        bitR.addRange(i, i + res[i] - 1, 1);
    }
    ll ans = 0;
    for(int i = 3; i < res.size() - 1; ++i) {
        if(t[i] == '#')
            ans += (ll)bitR.query(i-1) * bitL.query(i+1);
    }
    printf("%lld\n", ans);
}

int main() {
    scanf("%s", s);
    len = strlen(s);
    Manacher(s, ans);
    return 0;
}

欢迎留言