Для данного слова преобразовать его в палиндром с минимальным добавлением к нему букв

Сначала создайте функцию для проверки строки на палиндромность, помня, что «a» и «aa» являются палиндромами. Это палиндромы, да ???

Если входные данные являются палиндромом, вернуть его (необходимо добавить 0 символов) Цикл от x [длина] до x [1], проверяющий, является ли подмножество строки x [i] .. x [длина] палиндромом, найти самый длинный палиндром.

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

коко => с + око => с + око + с

mmmeep => mmmee + p => mmmee + p + eemmm

Хорошо! Вот моя вторая попытка.

Идея состоит в том, что мы хотим узнать, сколько символов в конце строки можно повторно использовать при добавлении дополнительных символов для завершения палиндрома. Для этого мы будем использовать модификацию алгоритма сопоставления строк KMP. Используя KMP, мы ищем обратную сторону исходной строки. Как только мы дойдем до самого конца строки, у нас будет как можно больше совпадений между обратной стороной строки и исходной строкой, которая встречается в конце строки. Например:

HELLO
    O

1010
 010

3202
 202

1001
1001

На этом этапе KMP обычно говорит «нет совпадений», если исходная строка не была палиндромом. Однако, поскольку в настоящее время мы знаем, какая часть обратной стороны строки была сопоставлена, мы можем вместо этого просто вычислить, сколько символов все еще отсутствует, а затем прикрепить их к концу строки. В первом случае нам не хватает LLEH. Во втором случае нам не хватает 1. В третьем нам не хватает 3. В последнем случае мы ничего не упускаем, поскольку исходная строка - это палиндром.

Время выполнения этого алгоритма - это время выполнения стандартного поиска KMP плюс время, необходимое для переворота строки: O (n) + O (n) = O (n).

Итак, теперь рассуждаем о правильности. Это потребует некоторых усилий. Рассмотрим оптимальный ответ:

   | original string | | extra characters |

Предположим, мы читаем это в обратном порядке от конца, что означает, что мы читаем, по крайней мере, обратную сторону исходной строки. Часть этой перевернутой струны проходит назад внутрь самой исходной струны. Фактически, чтобы минимизировать количество добавляемых символов, это должно быть максимально возможное количество символов, которое оканчивается самой строкой. Мы можем увидеть это здесь:

   | original string | | extra characters |
           | overlap |

Итак, что происходит на нашем шаге KMP? Что ж, при поиске перевернутой строки внутри себя, KMP всегда будет сохранять как можно дольше совпадение, поскольку оно работает по строке. Это означает, что, когда KMP достигает конца строки, совпадающая часть, которую он поддерживает, будет самым длинным из возможных совпадений, поскольку KMP перемещает вперед только начальную точку совпадения кандидата в случае сбоя. Следовательно, у нас есть максимально возможное перекрытие, поэтому мы получим минимально возможное количество символов, необходимое в конце.

Я не уверен на 100%, что это работает, но похоже, что это работает во всех случаях, когда я могу это сделать. Доказательство правильности кажется разумным, но оно немного сложное, потому что формальное доказательство на основе KMP, вероятно, будет немного сложным.

Надеюсь это поможет!

Чтобы ответить, я бы выбрал такой наивный подход:

1. когда нам нужно 0 символов? когда нить это палиндром
2. когда нам нужен 1 персонаж? когда кроме первой строки символов является палиндром
3. когда нам нужно 2 символа? если кроме двух начальных символов строка является палиндромом
4. и т.п ...

Итак, алгоритм может быть

  for index from 1 to length
   if string.right(index) is palindrome
    return string + reverse(string.left(index))
   end
  next

редактировать

Я не особо разбираюсь в Python, но простая реализация приведенного выше псевдокода могла бы быть

>>> def rev(s): return s[::-1]
... 
>>> def pal(s): return s==rev(s)
... 
>>> def mpal(s):
...  for i in range(0,len(s)):
...   if pal(s[i:]): return s+rev(s[:i])
... 
>>> mpal("cdefedcba")
'cdefedcbabcdefedc'
>>> pal(mpal("cdefedcba"))
True

Простое решение с линейным временем.

Назовем нашу строку S.

Пусть f (X, P) будет длиной самого длинного общего префикса X и P. Вычислить f (S [0], rev (S)), f (S [1], rev (S)), ... где S [k] - суффикс S, начинающийся с позиции k. Очевидно, вы хотите выбрать такое минимальное k, чтобы k + f (S [k], rev (S)) = len (S). Это означает, что вам просто нужно добавить k символов в конце. Если k равно 0, жало уже является палиндромом. Если k = len (S), вам нужно добавить полностью обратное.

Нам нужно быстро вычислить f (S [i], P) для всех S [i]. Это сложная часть. Создайте суффиксное дерево S. Пройдите по дереву и обновите каждый узел длиной самого длинного общего префикса с P. Значения на листьях соответствуют f (S [i], P).