Почти палиндром

[Skyfall]

Слово называется палиндромом, если его первая буква совпадает с последней, вторая – с предпоследней и т.д. Например: "abba", "madam", "x".

Для заданного числа K слово называется почти палиндромом, если в нем можно изменить не более K любых букв так, чтобы получился палиндром. Например, при $K=2$ слова "reactor", "kolobok", "madam" являются почти палиндромами (подчеркнуты буквы, заменой которых можно получить палиндром).

Подсловом данного слова являются все слова, получающиеся путем вычеркивания из данного нескольких (возможно, одной или нуля) первых букв и нескольких последних. Например, подсловами слова "cat" являются слова "c", "a", "t", "ca", "at" и само слово "cat" (а "ct" подсловом слова "cat" не является).

Требуется для данного числа K определить, сколько подслов данного слова S являются почти палиндромами.

Входные данные
В первой строке вводятся два натуральных числа:N ($1\leqslant N \leqslant 5000$) – длина слова и K ($0 \leqslant K \leqslant N$).
Во второй строке содержится слово S, состоящее из N строчных латинских букв.
Выходные данные
Требуется вывести одно число – количество подслов слова S, являющихся почти палиндромами (для данного K).

Примеры
входные данные
5 1
abcde
выходные данные
12
входные данные
3 3
aaa
выходные данные
6

Ограничение по времени, сек: 1
Ограничение по памяти, мегабайт: 64

В обсуждении говорили о методах (скольжения и отрезков), но мне они незнакомы и найти их я не смог. Если они в самом деле тут нужны, подскажите, где почитать о них. :)
Я так понимаю, что задачу можно решить с помощью алгоритма Манакера, но как его модифицировать непонятно.

[Gassa]

По-моему, это решается за $O(n^2)$ безо всякого алгоритма Манакера. Можно даже память не тратить.

Каждая подстрока данной строки характеризуется центром и длиной. Зафиксируем центр палиндрома (символ или место между символами) и будем наращивать длину. Если мы знаем, что для подстроки $s[i .. j]$ нужно поменять $X$ символов, чтобы она стала палиндромом, то для подстроки $s[i-1 .. j+1]$ нужно поменять те же $X$ символов — и ещё плюс один, если $s[i-1] \ne s[j+1]$. Затем делаем то же самое для подстроки $s[i-2 .. j+2]$, и так далее.

В целом решение состоит в том, чтобы перебрать центры. Для каждого центра, пока текущее значение $X$ не больше $K$ и пока мы не упёрлись в край данной строки — увеличиваем ответ и наращиваем длину.

Можно назвать это решение динамикой по подотрезкам: ответ для каждого отрезка (то есть подстроки) получается из ответа для меньшего отрезка.

[Skyfall]

Gassa, скажите, пожалуйста, почему наращивание с двух сторон одновременно покрывает все случаи (все подслова)?
Может, я Вас неправильно понял... Попробовал на первом примере из задачи, поправьте, пожалуйста:

abcde
k = 1
center: a
"a" и все, т.к. уперлись в край.
center: b
"b", "abc",
center: c
"c", "bcd",
center: d
"d", "cde"
center: e
"e"
Итого 8 вместо 12.

[arseniiv]

Skyfall в сообщении #1101354 писал(а):

скажите, пожалуйста, почему наращивание с двух сторон одновременно покрывает все случаи (все подслова)?

Если слово $\alpha$ не является палиндромом, то никакое слово $\beta\alpha\gamma, |\beta| = |\gamma|$, не является палиндромом, так что можно прерывать просмотр кандидатов для данного центра, как только в первый раз не сошлось.

Кстати, такая штука ведь упоминается и по той ссылке насчёт алгоритма Манакера, которую вы приводили.

Skyfall в сообщении #1101354 писал(а):

Попробовал на первом примере из задачи, поправьте, пожалуйста:

Центрами могут быть и двусимвольные строки. Это тоже упоминается по ссылке.

Skyfall в сообщении #1101354 писал(а):

center: c
"c", "bcd",

А abcde? Хотя, если её прибавить к упущенным ab, abcd, bcde, de, получится уже 13.

[Skyfall]

arseniiv
Вот про двусимвольные строки я не подумал. С ними тогда появляются как раз пропущенные ab, bc, cd, de. Итого 12.
Значит, теперь я вижу решение таким:
Как и говорил Gassa, перебираем центры, а для каждого центра пробуем его нарастить (пока ошибок меньше K и не уперлись в край исходной строки). Только вот получается, что нужно два раза пройтись: для нечетного случая (центр - один символ) и четного случая (центр - два символа). Верно? Есть более оптимальный вариант?

arseniiv в сообщении #1101355 писал(а):

А abcde? Хотя, если её прибавить к упущенным ab, abcd, bcde, de, получится уже 13.

Мы не дойдем до случая abcde. Во-первых, центр у этого подслова (да, фактически совпадающего с исходным) - с. Когда в переборе центров (в нечетном случае) дойдем до с, то к ответу +1 (т.к. один символ тоже палиндром), далее пробуем нарастить и получаем bcd. Такое подслово нам подходит, т.к. в этом примере $K = 1$. Наращиваем дальше: abcde. В этот раз нужно уже изменить как минимум 2 символа, чтобы получить палиндром, а значит, с этим центром ("с") заканчиваем и переходим к следующему.

[Gassa]

Skyfall в сообщении #1101379 писал(а):

Только вот получается, что нужно два раза пройтись: для нечетного случая (центр - один символ) и четного случая (центр - два символа). Верно? Есть более оптимальный вариант?

Можно ещё, как и обычно в задаче про палиндромы, между каждыми двумя символами исходной строки вставить какой-нибудь (один и тот же) непечатный символ. То есть, например, из abcde сделать a*b*c*d*e. Тогда можно рассматривать только нечётный случай.

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

[arseniiv]

Skyfall в сообщении #1101379 писал(а):

Мы не дойдем до случая abcde.

А. Почему-то я подумал, что вы решили выписать все возможные подстроки, my bad.