Count doubles palindromes dans la séquence d'int donné

Question

Pour un numéro de contrôle de séquence int donné de doubles palindromes, où en double palindrome, nous entendons la séquence de deux mêmes palindromes sans rupture entre eux. Ainsi, par exemple:

1 0 1 1 0 1 0 1 nous avons 1 un palindrome qui apparaît 2 fois sans interruption,

1 0 1 5 1 0 1 0 1 nous avons 1 mais il est séparé

(à part les autres dans ces séquences palindromes)

données de test Exemple de problème est:

  

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

avec des réponses

  

8 0 9

Manacher est évident pour la mendicité, mais je ne suis pas sûr de ce qu'il faut faire ensuite. Toutes les idées ont apprécié. La complexité doit être inférieure à n ^ 2 je suppose.

EDIT: int est ici traité comme seul élément de l'alphabet

Answer 1

Comme vous le savez déjà un algorithme pour trouver tous les palindromes (qui BTW est assez impressionnant), tout ce que vous devez faire est le suivant. Notez qu'un « double palindrome » est aussi un palindrome:
inverser (PP) = inverse (P) inverse (P) = PP.

Alors parmi tous les palindromes vous trouverez (a,b) (où par (a,b) je veux dire un palindrome à la position de a position b), vous devez trouver (i,j,k) telle que (i,j), (j,k) et (i,k) sont tous palindromes et j-i=k-j. De manière équivalente, pour chaque (i,j) palindrome vous trouvez, il vous suffit de définir k = 2j-i, et vérifier si les deux (k,j) et (i,k) sont palindromes.

Si la première étape retourne M palindromes en tout, cela prend O (M) le temps (les supposant que vous stockés de telle sorte que vérifier si un existe palindrome est O (1)), donc O (n ² ) dans le pire des cas. Je crois que cela devrait être optimale dans le pire des cas (considérer une chaîne de tous les 1).

Answer 2

Je commencerais avec 2 collections:

• une collection de séquences 'croissance'
• un ensemble de séquences 'rétrécissement'

L'algorithme fonctionne comme ceci:

• Dans un premier temps les deux collections sont vides
• Manipulez les valeurs de celui vectoriel par un, supposons que nous cherchons maintenant à la valeur V
• Boucle sur toutes les séquences « » de plus en plus
  • Si la dernière valeur d'une séquence de croissance est égal à V, copier la séquence croissante pour la collection de séquences rétrécissement, enlever V à partir de la fin de la nouvelle séquence de rétrécissement
  • Si l'une-but-dernière valeur de la séquence de croissance est égal à V, la copie de la séquence croissante pour la collection de séquences rétrécissement, retirer les 2 derniers éléments (V et le dernier) à partir de la séquence rétrécissement
• Boucle sur toutes les séquences « » rétrécissement
  • Si la dernière valeur de la séquence rétrécissement est égale à V, retirez-le de la séquence rétrécissement. Si une séquence rétrécissement devient vide, nous avons trouvé un palindrome.
  • Si la dernière valeur de la séquence rétrécissement est pas égal à V, supprimer cette séquence rétrécissement
• Enfin faire une nouvelle séquence croissante composée de seulement V

En fait, les séquences de croissance sont des séquences qui pourraient devenir un palindrome une fois, alors que les séquences diminue sont « partiellement » un palindrome.