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

Определение:

Палиндромом (англ. Palindrome) называется строка, которая одинаково читается как слева направо, так и справа налево.

Задача:

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

Алгоритм

Идея

Для каждой позиции в строке [math]s[/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].

См. также

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