結果

問題 No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
ユーザー pekempeypekempey
提出日時 2016-12-16 12:23:03
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 415 ms / 2,000 ms
コード長 5,237 bytes
コンパイル時間 2,145 ms
コンパイル使用メモリ 183,928 KB
実行使用メモリ 69,400 KB
最終ジャッジ日時 2024-11-30 10:22:50
合計ジャッジ時間 7,717 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 63 ms
15,676 KB
testcase_06 AC 300 ms
68,548 KB
testcase_07 AC 66 ms
16,376 KB
testcase_08 AC 291 ms
66,480 KB
testcase_09 AC 287 ms
67,780 KB
testcase_10 AC 291 ms
67,424 KB
testcase_11 AC 287 ms
67,052 KB
testcase_12 AC 213 ms
49,292 KB
testcase_13 AC 167 ms
37,904 KB
testcase_14 AC 305 ms
69,248 KB
testcase_15 AC 296 ms
68,876 KB
testcase_16 AC 217 ms
66,876 KB
testcase_17 AC 219 ms
67,380 KB
testcase_18 AC 341 ms
69,316 KB
testcase_19 AC 262 ms
69,400 KB
testcase_20 AC 297 ms
69,200 KB
testcase_21 AC 415 ms
69,316 KB
32_ratsliveonnoevilstar.txt AC 318 ms
69,148 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