0

文字列内の長さ「plen」の回文数(最大で30000)を見つけなければならないという質問を解決しようとしていました。ローリングハッシュ手法を使用して、長さplenのすべてのサブストリングとその逆のハッシュを計算することを考えました。ハッシュが一致する場合、定数の選択で十分であることを期待して、同等であると想定します。以下は私の実装です、私はめちゃくちゃになっているようです。単純な場合にも機能しません。誰かが私の間違いを教えてもらえますか?ありがとう。

int MUL = 37;
int MOD = 9999991;

for(int i = 1 , pwr = 1 ; i < plen ; i++) pwr = (pwr * MUL) % MOD;
long long hash = number[0];
long long revHash = number[plen - 1];
for(int i = 1 ; i < plen  ; i++)
{
    hash = (MUL*hash + number[i])%MOD;
    revHash = (revHash*MUL + number[plen - i - 1])%MOD;

}

cout << hash << " " << revHash <<"\n";

int cnt = (hash == revHash);

for(int i = plen ; i < numbers ; i++)
{
    hash = (hash + (MOD - pwr)*number[i - plen])%MOD;
    hash = (hash*MUL + number[i])%MOD;


    revHash = ((revHash + MOD - number[i - plen]))%MOD;
    revHash = (revHash + pwr*number[i])%MOD;

    cnt += (hash == revHash);

    cout << hash << " " << revHash << "\n";

}
4

0 に答える 0