Подсчет двойных палиндромов в заданной последовательности int

Question

Для заданной последовательности int проверьте число двойных палиндромов, где под двойным палиндромом мы подразумеваем последовательность двух одинаковых палиндромов без перерыва между ними. Так, например:

в 1 0 1 1 0 1 мы имеем 1 0 1 в качестве палиндрома, который появляется 2 раза без перерыва,

в 1 0 1 5 1 0 1 у нас есть 1 0 1, но он отделен

(кроме других палиндромов в этих последовательностях)

Пример тестовых данных проблемы:

3

12 0 1 1 0 0 1 1 0 0 1 1 0

12 1 0 1 0 1 0 1 0 1 0 1 0

6 3 3 3 3 3 3

с ответами

8 0 9

Манахер очевиден для попрошайничества, но я не уверен, что делать дальше. Любые идеи приветствуются. Сложность должна быть ниже n ^ 2, я думаю.

РЕДАКТИРОВАТЬ: int здесь рассматривается как отдельный элемент алфавита

Answer 1

Поскольку вы уже знаете алгоритм поиска всех палиндромов (что кстати довольно круто), все, что вам нужно сделать, это следующее.Обратите внимание, что «двойной палиндром» также является палиндромом:
реверс (PP) = реверс (P) реверс (P) = PP.

Таким образом, среди всех палиндромов (a,b) вы найдете (где по (a,b) Я имею в виду палиндром из положения a в положение b), вам нужно найти (i,j,k) такой, что (i,j), (j,k) и (i,k) - все палиндромы и j-i=k-j.Эквивалентно, для каждого найденного вами палиндрома (i,j) вам просто нужно установить k = 2j-i и проверить, являются ли (k,j) и (i,k) палиндромами.

Если первый шаг возвращает M палиндромов всего,на это уходит O (M) времени (при условии, что вы сохранили их таким образом, чтобы проверить, существует ли палиндром, является O (1)), поэтому O (n ² ) в худшем случае.Я считаю, что это должно быть оптимальным в худшем случае (рассмотрим строку всех 1).

Answer 2

Я бы начал с 2 коллекций:

• коллекция «растущих» последовательностей
• коллекция «сокращающихся» последовательностей

Алгоритм работает так:

• Изначально обе коллекции пусты
• Обрабатывать значения вектора по одному, предположим, что мы сейчас смотрим на значение V
• Цикл по всем «растущим» последовательностям
  • Если последнее значение растущей последовательности равно V, скопируйте растущую последовательность в коллекцию сокращающих последовательностей, удалите V из конца новой сокращающейся последовательности
  • Если значение последней последовательности растущей последовательности равно V, скопируйте растущую последовательность в коллекцию сокращающихся последовательностей, удалите последние 2 элемента (V и последний) из сокращающей последовательности
• Зацикливание на всех «сокращающихся» последовательностях
  • Если последнее значение последовательности сжатия равно V, удалите его из последовательности сжатия. Если последовательность сокращения становится пустой, мы нашли палиндром.
  • Если последнее значение последовательности сжатия не равно V, удалить эту последовательность сжатия
• Наконец, создайте новую растущую последовательность, состоящую только из V

На самом деле растущие последовательности представляют собой последовательности, которые могут стать палиндромом один раз, тогда как сокращающиеся последовательности «частично» являются палиндромом.