結果

問題 No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
ユーザー pekempeypekempey
提出日時 2016-12-16 12:23:03
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 406 ms / 2,000 ms
コード長 5,237 bytes
コンパイル時間 2,300 ms
コンパイル使用メモリ 183,092 KB
実行使用メモリ 69,428 KB
最終ジャッジ日時 2024-05-07 16:06:00
合計ジャッジ時間 7,347 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 61 ms
15,672 KB
testcase_06 AC 289 ms
68,384 KB
testcase_07 AC 65 ms
16,376 KB
testcase_08 AC 281 ms
66,416 KB
testcase_09 AC 275 ms
67,780 KB
testcase_10 AC 284 ms
67,560 KB
testcase_11 AC 275 ms
67,128 KB
testcase_12 AC 205 ms
49,332 KB
testcase_13 AC 162 ms
37,824 KB
testcase_14 AC 298 ms
69,212 KB
testcase_15 AC 282 ms
68,788 KB
testcase_16 AC 210 ms
66,988 KB
testcase_17 AC 213 ms
67,352 KB
testcase_18 AC 333 ms
69,428 KB
testcase_19 AC 253 ms
69,224 KB
testcase_20 AC 291 ms
69,296 KB
testcase_21 AC 406 ms
69,148 KB
32_ratsliveonnoevilstar.txt AC 305 ms
69,312 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

struct RollingHash {
    long long mod, base;
    vector<long long> h, p;

    RollingHash(string s, long long mod, long long base) : mod(mod), base(base), h(s.size() + 1), p(s.size() + 1, 1) {
        for (int i = 0; i < s.size(); i++) {
            h[i + 1] = (h[i] * base + s[i]) % mod;
            p[i + 1] = p[i] * base % mod;
        }
    }

    long long substr(int start, int len) {
        return (h[start + len] + mod - h[start] * p[len] % mod) % mod;
    }
};

struct HashPalindrome {
    int mod = 1e9 + 7;
    int n;
    vector<RollingHash> rh;

    HashPalindrome(string s) {
        n = s.size() * 2 + 1;
        string t = s;
        reverse(t.begin(), t.end());
        for (int i = 0; i < 3; i++) {
            rh.emplace_back(s + "$" + t, mod, rand() + 2);
        }
    }

    bool isPalindrome(int start, int len) {
        for (int i = 0; i < 3; i++) {
            if (rh[i].substr(start, len) != rh[i].substr(n - start - len, len)) {
                return false;
            }
        }
        return true;
    }
};

vector<int> manacher(string s) {
    int i = 0;
    int j = 0;
    vector<int> rad(s.size());
    while (i < s.size()) {
        while (i - j >= 0 && i + j < s.size() && s[i - j] == s[i + j]) {
            j++;
        }
        rad[i] = j;
        int k = 1;
        while (i - k >= 0 && i + k < s.size() && k + rad[i - k] < j) {
            rad[i + k] = rad[i - k];
            k++;
        }
        i += k;
        j -= k;
    }
    return rad;
}

vector<int> oddPalindromeSuffix(string s) {
    vector<int> rad = manacher(s);
    vector<int> res(s.size(), 1e9);
    for (int i = 1; i < s.size(); i++) {
        int r = min(i - 1, rad[i]);
        res[i + r - 1] = min(res[i + r - 1], i);
    }
    for (int i = (int)s.size() - 2; i >= 0; i--) {
        res[i] = min(res[i], res[i + 1]);
    }
    for (int i = 0; i < res.size(); i++) {
        res[i] = (i - res[i]) * 2 + 1;
    }
    return res;
}

vector<int> longestPalindromeSuffix(string s) {
    string ss;
    for (int i = 0; i < s.size() - 1; i++) {
        ss += s[i];
        ss += '$';
    }
    ss += s.back();
    vector<int> odd = oddPalindromeSuffix(ss);
    vector<int> res(s.size());
    for (int i = 0; i < s.size(); i++) {
        res[i] = (odd[i * 2] + 1) / 2;
    }
    return res;
}

vector<int> zAlgorithm(string s) {
    vector<int> z(s.size());
    z[0] = s.size();
    int i = 1;
    int j = 0;
    while (i < s.size()) {
        while (i + j < s.size() && s[i + j] == s[j]) {
            j++;
        }
        z[i++] = j;
        if (j == 0) {
            continue;
        }
        j--;
        int k = 1;
        while (i < s.size() && z[k] < j) {
            z[i++] = z[k++];
            j--;
        }
    }
    return z;
}

int main() {
    string s;
    cin >> s;
    string t = s;
    reverse(t.begin(), t.end());
    int n = s.size();

    vector<bool> bad(n);
    vector<int64_t> cnt(n + 2);
    vector<int> z = zAlgorithm(s);

    HashPalindrome rh(s);

    vector<int> lps = longestPalindromeSuffix(s);

    // Hypothesis. 
    // 回文の集合を Pal とする。
    // Pal^2の文字列 X が二種類の回文分解 AB,CD を持つならば、
    // 以下の条件のいずれかを満たすXの接頭辞X'が存在する。
    // ・X in X'*, where X' in Pal
    // ・X in X'*, where X' in Pal^2

    // 二種類以上の回文分解を持たない最小単位の接頭辞を得ることができれば、
    // その繰り返しとして他のPal^2型文字列は表現できる。
    for (int i = 1; i < n; i++) {
        if (bad[i]) {
            continue;
        }
        if (rh.isPalindrome(0, i)) {
            for (int j = 2; i * j < n; j++) {
                if (z[i * (j - 1)] < i) {
                    break;
                }
                cnt[i * j + 1] += j - 1;
                bad[i * j] = true;
            }
        }
    }
    int pre = 1;
    for (int i = 2; i <= n - 2; i++) {
        if (!bad[i]) {
            int suf = lps[i - 1];
            bool ok = false;
            // Hypothesis
            // 文字列XがPal^2であることと以下のいずれかが成り立つことは同値である。
            // ・Xは最長回文接頭辞+あまりの文字列に分解可能
            // ・Xはあまりの文字列+最長回文接尾辞に分解可能
            if (rh.isPalindrome(0, pre) && rh.isPalindrome(pre, i - pre)) {
                ok = true;
            }
            if (rh.isPalindrome(0, i - suf) && rh.isPalindrome(i - suf, suf)) {
                ok = true;
            }
            if (ok) {
                for (int j = 1; i * j < n; j++) {
                    if (z[i * (j - 1)] < i) {
                        break;
                    }
                    cnt[i * j + 1] += j;
                    bad[i * j] = true;
                }
            }
        }
        if (rh.isPalindrome(0, i)) {
            pre = i;
        }
    }

    for (int i = 0; i < n - 1; i++) {
        cnt[i + 1] += cnt[i];
    }

    int64_t ans = 0;
    for (int i = 0; i < n; i++) {
        if (rh.isPalindrome(i, n - i)) {
            ans += cnt[i];
        }
    }
    cout << ans << endl;
}
0