Количество подпалиндромов в строке

Задача:

Пусть дана строка [math]s[/math], требуется посчитать количество палиндромов в ней за [math]O(|s|\cdot\log{|s|)}[/math] c помощью хешей.

Алгоритм

Идея

Рассмотрим сначала задачу поиска палиндромов нечетной длины. Для каждой позиции в строке [math]s[/math] найдем длину наибольшего палиндрома с центром в этой позиции. Очевидно, что если строка [math]t[/math] является палиндромом, то строка полученная вычеркиванием первого и последнего символа из [math]t[/math] также является палиндромом. Поэтому длину палиндрома можно искать бинарным поиском. Для сохранения асимптотики проверку совпадения левой и правой половины требуется выполнить за [math]O(1)[/math]. Для этого можно воспользоваться методом хеширования.

Для палиндромов четной длины алгоритм такой же, только следует проверять вторую строку со сдвигом на единицу, при этом мы не посчитаем никакой палиндром дважды из-за четности-нечетности палиндромов.

Псевдокод

int binarySearch(s : string, center, shift : int):
    //shift = 0 при поиске палиндрома нечетной длины, иначе shift = 1
    int l = -1, r = s.length, m = 0
    while r - l != 1
        m = l + (r - l) / 2
        if hash(s[center - m..center]) == hash(reverse(s[center + shift..center + shift + m]))
            l = m
        else
            r = m
    return r

int palindromesCount(s : string):
    int ans = 0
    for i = 0 to s.length
        ans += binarySearch(s, i, 0) + binarySearch(s, i, 1)
    return ans

Избавление от коллизий

У хешей есть один недостаток — коллизии, у двух разных строк хеши могут совпадать. Абсолютно точно проверить две подстроки на совпадение можно с помощью суффиксного массива. Для этого построим суффиксный массив для строки [math]s + \# + reverse(s)[/math], при этом сохраним промежуточные результаты классов эквивалентности [math]c[/math]. Пусть нам требуется проверить на совпадение подстроки [math]s[i..i + l][/math] и [math]s[j..j + l][/math]. Разобьем каждую нашу строку на две пересекающиеся подстроки длиной [math]2^k[/math], где [math]k = \lfloor \log{l} \rfloor[/math]. Тогда наши строки совпадают, если [math]c[k][i] = c[k][j][/math] и [math]c[k][i + l - 2^k] = c[k][j + l - 2^k][/math].

Итоговая асимптотика алгоритма: предподсчет за построение суффиксного массива и [math]O(\log(|s|)[/math] на запрос, если предподсчитать все [math]k[/math], то [math]O(1)[/math].

См. также

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

Источники информации

• MAXimal :: algo :: Суффиксный массив