Почему мой хеш строки даёт неверные сравнения — переполнение или знак символа?
Написал полиномиальный хеш по модулю 1e9+9, но сравнения подстрок иногда дают неверный результат даже на простых строках без коллизий. Подозреваю баг, а не вероятностную коллизию. Вот кусок:
long long h = 0;
for (char c : s) h = h * base + c; // без mod!
Что здесь не так?
2 ответа
Тут сразу несколько детерминированных багов, не коллизии:
-
Нет взятия по модулю внутри цикла —
h * base + cбыстро переполняетlong long(для строки длиннее ~12 символов при base=131). Переполнение знакового типа — UB, и значения «портятся» непредсказуемо. Нужноh = (h * base + c) % MOD;. -
Промежуточное умножение переполняет даже при mod, если
MOD ~ 1e9:h * baseдо~1e9 * 131 ≈ 1.3e11влезает в long long, это ок. Но еслиMOD ~ 1e18(как2^61-1),h*baseпереполнит long long → нужен__int128или специальныйmulmod. -
Знак символа:
charможет быть знаковым, и для символов с кодом > 127 (UTF-8, кириллица в байтах)cстанет отрицательным, добавив отрицательный вклад. Приводите кunsigned char:(h * base + (unsigned char)c) % MOD.
Исправленный вариант:
const long long MOD = 1e9 + 9, base = 131;
long long h = 0;
for (unsigned char c : s) h = (h * base + c) % MOD;
По асимптотике ничего не меняется — O(n), просто теперь корректно.
Самый коварный из трёх — знаковый char, потому что он не виден на маленьких латинских тестах и вылезает только на кириллице/бинарных данных. Возьмите за привычку всегда читать символы как unsigned char или прибавлять смещение (c - 'a' + 1). Прибавление именно +1, а не +0, ещё и спасает от того, что символ 'a'→0 обнуляет вклад ведущих букв (строки a, aa, aaa иначе дают одинаковый хеш 0).