Question

У Азизхана есть строка S. Его интересует сколько есть подстрок четной длины у строки S, которые являются палиндромами. Одинаковые подстроки начинающие с разных позиций считаются разными. Формат входных данных Единственная строка входного файла содержит одну строку S состоящее из строчных букв английского алфавита (1 <= длина S <= 100000). Формат выходных данных Выведите ответ к задаче. Помагите плиз

Answer 1

Наивный алгоритм: используя два вложенных цикла, проверить все подстроки, являются ли они палиндромами. Такой алгоритм будет работать O(|S|^2), что при ограничении |S| <= 10^5 потребует примерно 10^10 / 2 сравнений, что достаточно долго.

Оптимизация: в центре у палиндрома четной длины всегда пара одинаковых символов. Их можно найти, а затем увеличивать длину до тех пор, пока это возможно. Плюс этого наблюдения в том, что если пара попадется не в центре, то максимальная длина подстроки-палиндрома с центром в этой паре, будет ограничена сверху. Однако в худшем случае (все символы одинаковы) всё равно придется произвести немалое число сравнений.

Однако задачу можно решить и за линейное время. Например, существует алгоритм Манакера, основанный на том, что можно использовать информацию, что часть строки является палиндромом. А именно, если в длинную-длинную строку-палиндром входит другая подстрока-палиндром, то можно не начинать проверку заново, а использовать уже имеющуюся информацию.

Пример 1: "длинная" подстрока-палиндром:
cbbaabbaabbc
в которой известна подстрока-палиндром. Тогда в строке есть симметричная подстрока-палиндром:
cbbaabbaabbc
Пример 2: "длинная" подстрока палиндром:
bbaabbaabbaa
Зная, что в ней есть подстрока-палиндром
bbaabbaabbaa,
можно явные сравнения для подстроки с центром в
bbaabbaabbaa
начинать уже с 
bbaabbaabbaa

Если не хочется писать самостоятельно, алгоритм Манакера легко находится.

Answer 2

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

Создадим двумерный массив dp размером (n+1) x (n+1), где n - длина строки S. Значение dp[i][j] будет равно 1, если подстрока, начинающаяся с позиции i и заканчивающаяся на позиции j, является палиндромом, и 0 в противном случае.

Инициализируем массив dp следующим образом: - dp[i][i] = 1 для всех i от 1 до n (подстроки длины 1 являются палиндромами) - dp[i][i+1] = 1, если S[i] = S[i+1] для всех i от 1 до n-1 (подстроки длины 2 с одинаковыми символами являются палиндромами)

Затем, используя заполненный массив dp, мы можем вычислить значения dp[i][j] для всех i и j, где i < j. Для этого будем использовать следующее рекуррентное соотношение: - dp[i][j] = 1, если S[i] = S[j] и dp[i+1][j-1] = 1 (подстрока между символами i и j является палиндромом)

Для подсчета количества подстрок четной длины, являющихся палиндромами, мы будем увеличивать счетчик каждый раз, когда значение dp[i][j] равно 1 и длина подстроки (j - i + 1) четная.

В итоге, сумма всех значений счетчика будет являться ответом к задаче.

Пример кода на Python:

s = input()  # считываем строку S
n = len(s)

dp = [[0] * (n+1) for _ in range(n+1)]  # создаем массив dp

# инициализация массива dp
for i in range(1, n+1):
    dp[i][i] = 1
for i in range(1, n):
    if s[i-1] == s[i]:
        dp[i][i+1] = 1

count = 0  # счетчик количества палиндромов

# вычисление значений dp и подсчет палиндромов
for i in range(1, n+1):
    for j in range(i+1, n+1):
        if s[i-1] == s[j-1] and dp[i+1][j-1] == 1:
            dp[i][j] = 1
            if (j - i + 1) % 2 == 0:  # если длина подстроки четная
                count += 1

print(count)  # выводим ответ

Надеюсь, это поможет вам решить задачу! Если у вас возникнут еще вопросы, не стесняйтесь задавать.