C++で解く「異なるエコー部分文字列」の数え方 ― ローリングハッシュによる効率的アプローチ

問題の概要

文字列 S が与えられたとき、「ある文字列をそれ自身と連結した形（AA の形）」として表すことができる、異なる空でない部分文字列の個数を求めることを考えます。

たとえば入力が "elloelloello" の場合、出力は 5 になります。条件を満たす部分文字列の例としては、"ll" のほかに、"ello"、"lloe"、"loel"、"oell" のようなものが挙げられます。

アプローチ：ローリングハッシュ

すべての部分文字列同士を直接比較すると非常に非効率なため、ここではローリングハッシュ（Rabin–Karp 法）を活用します。ウィンドウを1文字スライドさせるたびにハッシュ値を O(1) で更新できるため、「長さ i/2 の前半部分」と「後半部分」のハッシュが一致するかどうかを高速に判定できます。

※ ハッシュの一致は確率的な判定であり、厳密には衝突の可能性がありますが、十分に大きな素数（ここでは 10⁹ + 7）を法とすることで、実用上はほぼ問題なく動作します。

準備：定数の定義

• prime := 31 …… ハッシュ計算に用いる基数
• m := 10⁹ + 7 …… ハッシュの剰余を取る大きな素数

fastPow()：べき乗の高速計算

引数として base と power を受け取り、繰り返し二乗法（バイナリ法）によって base^power mod m を O(log power) で計算します。

1. res := 1 で初期化する
2. power > 0 の間、次を繰り返す：
   　・power の最下位ビットが 1 ならば res := res × base とし、mod m を適用する
   　・base := base² とし、mod m を適用する
   　・power := power ÷ 2 とする
3. res を返す

createHashValue()：ハッシュ値の生成

文字列 s とその長さ n を受け取り、result := 0 としたうえで、i = 0 ～ n−1 について「result := result + s[i] × primeⁱ」を加算し、都度 mod m を適用して result を返します。いわゆる多項式ローリングハッシュの基本的な形です。

recalculateHash()：ハッシュの再計算

ウィンドウが1文字スライドした際に、ハッシュを作り直す代わりに O(1) で更新します。具体的には、先頭文字 old の寄与を差し引き、mod m 上の逆元（フェルマーの小定理より fastPow(prime, m − 2)）を掛けて桁を詰めたあと、末尾に新しい文字 newC を prime^{patLength−1} の重みで加えます。

メイン処理の流れ

1. n := 文字列の長さとし、結果を格納する集合 ans を用意する
2. 偶数長 i = 2, 4, …, n のそれぞれについて、先頭のウィンドウ [0, i) を対象に、前半 [0, i/2) のハッシュ hash1 と後半 [i/2, i) のハッシュ hash2 を createHashValue() で生成する
3. ウィンドウを1文字ずつ右へスライドさせながら（s1, e1, s2, e2 をそれぞれ +1）、hash1 == hash2 であれば hash1 を ans に挿入する。スライド時のハッシュ更新には recalculateHash() を使用する
4. ループを抜けたあとも、最後のウィンドウに対して同様の一致判定を行う
5. 最後に ans のサイズを返す。これが異なるエコー部分文字列の総数となる

実装例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli prime = 31;
const lli m = 1e9 + 7;
class Solution {
    public:
    lli fastPow(lli base, lli power){
        lli res = 1;
        while (power > 0) {
            if (power & 1) {
                res = res * base;
                res %= m;
            }
            base *= base;
            base %= m;
            power >>= 1;
        }
        return res;
    }
    lli createHashValue(string s, lli n){
        lli result = 0;
        for (lli i = 0; i < n; i++) {
            result += (lli)(s[i] * fastPow(prime, i));
            result %= m;
        }
        return result;
    }
    lli recalculateHash(char old, char newC, lli oldHash, lli patLength){
        lli newHash;
        newHash = oldHash - (lli)old;
        newHash *= fastPow(prime, m - 2);
        newHash += ((lli)newC * fastPow(prime, patLength - 1));
        newHash %= m;
        return newHash;
    }
    int distinctEchoSubstrings(string text){
        int n = text.size();
        set<int> ans;
        for (int i = 2; i <= n; i += 2) {
            string temp = "";
            for (int j = 0; j < i / 2; j++) {
                temp += text[j];
            }
            int hash1 = createHashValue(temp, i / 2);
            temp = "";
            for (int j = i / 2; j < i; j++) {
                temp += text[j];
            }
            int hash2 = createHashValue(temp, i / 2);
            for (int s1 = 0, e1 = i / 2, s2 = i / 2, e2 = i; e2 < n;
            s1++, s2++, e1++, e2++) {
                if (hash1 == hash2) {
                    ans.insert(hash1);
                }
                hash1 = recalculateHash(text[s1], text[e1], hash1,
                i / 2);
                hash2 = recalculateHash(text[s2], text[e2], hash2,
                i / 2);
            }
            if (hash1 == hash2) {
                ans.insert(hash1);
            }
        }
        return ans.size();
    }
};
main(){
    Solution ob;
    cout << (ob.distinctEchoSubstrings("elloelloello"));
}

入力

"elloelloello"

出力

5

計算量について

この実装では、各偶数長 i ごとに文字列を O(n) 回走査し、各ステップのハッシュ比較・更新は O(1) で行えるため、全体の時間計算量は O(n²) となります。必要な追加空間は、重複排除のためのハッシュ集合の分だけ消費します。