Нужно ли использовать символы маркера (символы между символами в заданной строке) при реализации алгоритма Манахера для самой длинной палиндромной подстроки?Алгоритм Манахера
Если да, что произойдет, если все 256 символов будут использованы?
Лично я считаю, что алгоритм сам по себе уже достаточно прост. Если вам удастся сделать это без маркеров, ваш код не будет выглядеть очень понятным.
К счастью, нет смысла. Алгоритм может работать для массивов любого типа. Как строка, это всего лишь массив символов. Просто начните с разбора вашей строки в массив типа, который будет подходящим для вашей кодировки по выбору, и вы хороши. Нет сложности, связанной с размером вашего типа данных.
В алгоритме Manacher используется свойство палиндрома, которое симметрично по центру. Центр поиска относительно прямой для строк с нечетной длиной. Добавление символа в строку длины длины гарантирует, что строка становится нечетной. Итак, если ваша строка имеет четную длину, тогда необходимо добавить символы
Зачем должно быть только 256 отдельных символов? Вы думаете об ASCII? Если да, почему бы не UTF-8, UTF-32 или даже почему ограничивать набор символов, а не использовать номера произвольной длины? – Aaron