Поиск наибольшего общего префикса двух строк бинарным поиском

#cpp #алгоритм #хеширование

Пишу сейчас задачу, для которой нужно уметь быстро находить наибольший общий префикс
двух строк. 

Решил реализовать это с помощью бинарного поиска: перебираем длину префикса и если
хеш этого префикса для двух строк совпадает, то двигаем границы вправо, чтобы найти
большую длину префикса, а иначе двигаем влево, чтобы посмотреть меньшую длину префикса.

Полиномиальный хеш как раз позволяет найти сначала хеш всей строки, а потом за 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'

    

Ответы

Ответ 1

Я нашёл решение. Думаю, это больше всё-таки похоже на костыль, но всё же.

Я предположил, что l в конце работы алгоритма бинарного поиска может быть больше
нужного, на самом деле не знаю, в каком случае, только на единицу. Это я предположил
исходя из того, что в более классической релизации бинарного поиска ответом может быть
как l = m + 1, так и просто m, если ответ был найден ещё до выхода из while.

Заменил в итоге это:

if(ha.get(0, l) == hb.get(0, l)) common = l + 1;
else common = 0;


На это:

int common;
int variant1 = l, variant2 = l - 1;
if(ha.get(0, variant1) == hb.get(0, variant1)) {
    common = variant1 + 1;
} else {
    if(l - 1 >= 0 && ha.get(0, variant2) == hb.get(0, variant2)) {
        common = variant2 + 1;
    } else {
        common = 0;
    }
}