Пишу сейчас задачу, для которой нужно уметь быстро находить наибольший общий префикс двух строк.
Решил реализовать это с помощью бинарного поиска: перебираем длину префикса и если хеш этого префикса для двух строк совпадает, то двигаем границы вправо, чтобы найти большую длину префикса, а иначе двигаем влево, чтобы посмотреть меньшую длину префикса.
Полиномиальный хеш как раз позволяет найти сначала хеш всей строки, а потом за O(1) находить хеш подстроки, что удобно для сравнения этих самых подстрок.
Но есть проблема: мой бинарный поиск напонятно по каким причинам находит неправильную длину префикса и я никак не могу это отдебагать.
В чём проблема?
Поиск префикса:
int d(string &a, string &b) {
StrHash ha(a), hb(b);
int mid, l = 0, r = min(a.size(), b.size()) - 1;
while(l < r) {
mid = (l + r) / 2;
if(ha.get(0, mid) == hb.get(0, mid)) {
l = mid + 1;
} else {
r = mid - 1;
}
}
int common;
///А тут мы проверяем, нашли мы префикс или нет.
if(ha.get(0, l) == hb.get(0, l)) common = l + 1;
else common = 0;
return common;
}
Тест с багом, находит ответ 0
:
s1 = 'aaaaa'
s2 = 'ab'