4

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

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

Полиномиальный хеш как раз позволяет найти сначала хеш всей строки, а потом за 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'
2
  • Так а за какое время выполняется инициализация вашего хэша, чтобы потом можно было "за O(1) находить хеш подстроки"? Если инициализация хэша требует линейного прохода всей строки, то какой во всем этом смысл, если сразу можно было линейным проходом найти префикс? Commented 12 янв. 2019 в 8:25
  • А, вижу обсуждение ниже... То есть никакого обоснованного ответа нет, кроме "я верю"... Отказать. Грамотно реализованное прямое сравнение будет работать намного быстрее. Commented 12 янв. 2019 в 8:28

1 ответ 1

2

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

Я предположил, что 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;
    }
}
1
  • Комментарии не предназначены для расширенной дискуссии; разговор перемещён в чат.
    – ЮрийСПб
    Commented 12 янв. 2019 в 10:08

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.