AtCoder Regular Contest 055 C - ABCAC

問題

arc055.contest.atcoder.jp

解法

ABCAC の 2 つ目の A の開始位置について全探索します。この位置を rp として, 最大で A の長さをどこまで長くできるか(lenA とする)を考えます。これはローリングハッシュを使って二分探索すればできます。

また, C についても文字列 S を逆から見れば 同様にローリングハッシュの二分探索を使って C の最大の長さ(lenC とする)を求められます。
A, C の長さを a, c とすると以下の条件が成り立っている必要があります(文字列 S の長さを n とします)。

• a+c = n-rp (rp から A, C を連結させて文字列が終わるので)
• a+c < rp (B という文字列が存在してないといけない)
• 1 <= a <= lenA, 1 <= c <= lenC

lenA, lenC の最大の長さを n-rp-1 とすれば A が rp からスタートする場合の ABCAC の場合の数は, max(0, lenA+lenC - (n-rp) + 1) で求められます(これ考えるのに時間かかった…イメージとしては, a 軸, c 軸の二次元平面を考えて, a+c = n-rp という直線を考えます)。

std::random_device rnd;
const ull mul[2] = {10000 + (rnd()%10000), 10000 + (rnd()%10000)};
const ull mod[2] = {1000000007, 1000000009};

class RollingHash {
public:
    RollingHash() {}
    template<class T>
    RollingHash(const T& s) {
        init(s);
    }
    template<class T>
    void init(const T& s) {
        n = s.size();
        for (int i = 0; i < 2; i++) {
            pow[i].resize(n+1);
            h[i].resize(n+1);
            pow[i][0] = 1; h[i][0] = 0;
        }
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                pow[i][j+1] = (mul[i]*pow[i][j]) % mod[i];
                h[i][j+1] = (s[j] + h[i][j]*mul[i]) % mod[i];
            }
        }
    }
    inline pair<ull, ull> hash(int i) const {return make_pair(h[0][i], h[1][i]);}
    // [l, r)
    inline pair<ull, ull> hash(int l, int r) const {
        ull p0 = (h[0][r] - (h[0][l]*pow[0][r-l]%mod[0]) + mod[0]) % mod[0];
        ull p1 = (h[1][r] - (h[1][l]*pow[1][r-l]%mod[1]) + mod[1]) % mod[1];
        return make_pair(p0, p1);
    }
private:
    int n;
    vector<ull> pow[2], h[2];
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    RollingHash rh(S);
    string T = S;
    reverse(T.begin(), T.end());
    RollingHash rht(T); 
    int n = S.size();
    ll ans = 0;
    for (int rp = 3; rp < n-1; rp++) {
        if (n-rp >= rp) continue;
        int lenA = [&]() {
            int low = 0, high = min(rp, n-rp)+1;
            while (high - low > 1) {
                const int med = (low+high)/2;
                if (rh.hash(0, med) == rh.hash(rp, rp+med)) low = med;
                else high = med;
            }
            return min(low, n-rp-1);
        }();
        int lenC = [&]() {
            int low = 0, high = min(rp, n-rp)+1;
            while (high-low > 1) {
                const int med = (low+high)/2;
                if (rht.hash(0, med) == rht.hash(n-rp, n-rp+med)) low = med;
                else high = med;
            }
            return min(low, n-rp-1);
        }();
        ans += max(0, (lenA+lenC)-(n-rp)+1);
        //cout << rp << " " << ans << endl;
    }
    cout << ans << endl;
    return 0;
}

B よりこっちのほうが発想はシンプル。ABCAC だけど ACAC の人のほうが多かった印象。