結果

問題 No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
ユーザー pekempeypekempey
提出日時 2016-12-16 12:23:03
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 419 ms / 2,000 ms
コード長 5,237 bytes
コンパイル時間 2,107 ms
コンパイル使用メモリ 182,256 KB
実行使用メモリ 69,136 KB
最終ジャッジ日時 2023-08-20 08:59:45
合計ジャッジ時間 7,860 ms
ジャッジサーバーID
(参考情報)
judge14 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,384 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 62 ms
15,608 KB
testcase_06 AC 296 ms
68,256 KB
testcase_07 AC 65 ms
16,056 KB
testcase_08 AC 291 ms
66,160 KB
testcase_09 AC 284 ms
67,628 KB
testcase_10 AC 286 ms
67,424 KB
testcase_11 AC 286 ms
66,860 KB
testcase_12 AC 211 ms
49,040 KB
testcase_13 AC 166 ms
37,736 KB
testcase_14 AC 303 ms
69,036 KB
testcase_15 AC 297 ms
68,592 KB
testcase_16 AC 216 ms
67,116 KB
testcase_17 AC 218 ms
67,356 KB
testcase_18 AC 338 ms
69,064 KB
testcase_19 AC 261 ms
69,088 KB
testcase_20 AC 298 ms
69,000 KB
testcase_21 AC 419 ms
69,136 KB
32_ratsliveonnoevilstar.txt AC 314 ms
69,060 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