Palindrome le plus long d’une chaîne en utilisant l’arbre des suffixes

J’essayais de trouver le plus long palindrome d’une chaîne. La solution de force brute prend du temps O (n 3). Je lis qu’il existe un algorithme de temps linéaire pour cela en utilisant des arbres de suffixe. Je connais bien les arbres de suffixe et je suis à l’aise pour les construire. Comment utilisez-vous le suffixe construit pour trouver le palindrome le plus long?

    Je crois que vous devez procéder de cette façon:

    Soit y 1 y 2y n ta chaîne (où y je suis des lettres).

    Créez l’arbre des suffixes généralisés de Sf = y 1 y 2y n $ et S r = y n y n – 1y 1 # (inversez les lettres et choisissez différents caractères de fin pour S f ($) et S r (#)) … où S f signifie “Ssortingng, Forward” et S r signifie “Ssortingng, Reverse” .

    Pour chaque suffixe i dans S f , trouvez l’ancêtre commun le plus bas avec le suffixe n – i + 1 dans S r .

    Ce qui va de la racine jusqu’à cet ancêtre commun le plus bas est un palindrome, car maintenant l’ancêtre commun le plus bas représente le plus long préfixe commun de ces deux suffixes. Rappeler que:

    (1) Un préfixe de suffixe est une souschaîne .

    (2) Un palindrome est une chaîne identique à son revers.

    (3) Ainsi, le plus long palindrome contenu dans une chaîne est exactement la plus longue sous-chaîne commune de cette chaîne et son inverse.

    (4) Ainsi, le plus long palindrome contenu dans une chaîne est exactement le plus long préfixe commun de toutes les paires de suffixes entre une chaîne et son inverse. C’est ce que nous faisons ici.

    EXEMPLE

    Prenons le mot banane .

    S f = banane $

    S r = ananab #

    Voici le suffixe généralisé de S f et S r , où le nombre à la fin de chaque chemin est l’index du suffixe correspondant. Il y a une petite erreur, le point commun à toutes les 3 twigs du parent de Blue_4 devrait être sur son bord entrant, à côté de n :

    entrer la description de l'image ici

    Le nœud intérieur le plus bas de l’arbre est la plus longue sous-chaîne commune de cette chaîne et son inverse. En regardant tous les nœuds intérieurs de l’arbre, vous trouverez donc le palindrome le plus long.

    Le plus long palindrome se trouve entre Green_0 et Blue_1 (c’est-à-dire banane et anana ) et est anana


    MODIFIER

    Je viens de trouver cet article qui répond à cette question.

    La solution linéaire peut être trouvée de cette façon ::

    Pré-requirejs:

    (1). Vous devez savoir comment construire le tableau de suffixes dans le temps O (N) ou O (NlogN).

    (2). Vous devez savoir comment trouver le tableau LCP standard, c.-à-d. LCP entre les suffixes adjacents i et i-1

    c’est à dire . LCP [i] = LCP (suffixe i dans le tableau sortingé, suffixe i-1 dans le tableau sortingé) pour (i> 0).

    Soit S la chaîne d’origine et S ‘ l’inverse de la chaîne d’origine. Prenons S = ” banane ” comme exemple. Puis sa chaîne inverse S ‘= ananab.

    Étape 1 : Concaténer S + # + S ‘ pour obtenir la chaîne Str, où # est un alphabet non présent dans la chaîne d’origine.

    Concatenated Ssortingng Str=S+#+S' Str="banana#ananab" 

    Étape 2: Construisez maintenant le tableau des suffixes de la chaîne Str.

    Dans cet exemple, le tableau de suffixes est:

     Suffix Number Index Sorted Suffix 0 6 #ananab 1 5 a#ananab 2 11 ab 3 3 ana#ananab 4 9 anab 5 1 anana#ananab 6 7 ananab 7 12 b 8 0 banana#ananab 9 4 na#ananab 10 10 nab 11 2 nana#ananab 12 8 nanab 

    Veuillez noter qu’un tableau de suffixes est un tableau d’entiers donnant les positions de départ des suffixes d’une chaîne dans l’ordre lexicographique. Ainsi, le tableau contenant Index de la position de départ est un suffixe Array.

    C’est SuffixArray [] = {6,5,11,3,9,1,7,12,0,4,10,2,8};

    Étape 3 : Comme vous avez réussi à construire le tableau des suffixes, trouvez maintenant les plus longs préfixes communs entre les suffixes adjacents .

     LCP between #ananab a#ananab is :=0 LCP between a#ananab ab is :=1 LCP between ab ana#ananab is :=1 LCP between ana#ananab anab is :=3 LCP between anab anana#ananab is :=3 LCP between anana#ananab ananab is :=5 LCP between ananab b is :=0 LCP between b banana#ananab is :=1 LCP between banana#ananab na#ananab is :=0 LCP between na#ananab nab is :=2 LCP between nab nana#ananab is :=2 LCP between nana#ananab nanab is :=4 

    Ainsi, le tableau LCP LCP = {0,0,1,1,3,3,5,0,1,0,2,2,4}.

    Où LCP [i] = Longueur du préfixe commun le plus long entre le suffixe i et le suffixe (i-1). (pour i> 0)

    Étape 4:

    Maintenant que vous avez construit un tableau LCP, utilisez la logique suivante.

      Let the length of the Longest Palindrome ,longestlength:=0 (Initially) Let Position:=0. for(int i=1;ilongestlength)) { //Note Actual Len=Length of original Input ssortingng . if((suffixArray[i-1]actuallen)||(suffixArray[i]actuallen)) { //print :Calculating Longest Prefixes b/w suffixArray[i-1] AND suffixArray[i] longestlength=LCP[i]; //print The Longest Prefix b/w them is .. //print The Length is :longestlength:=LCP[i]; Position=suffixArray[i]; } } } So the length of Longest Palindrome :=longestlength; and the longest palindrome is:=Str[position,position+longestlength-1]; 

    Exemple d’exécution ::

      actuallen=Length of banana:=6 Len=Length of "banana#ananab" :=13. Calculating Longest Prefixes b/wa#ananab AND ab The Longest Prefix b/w them is :a The Length is :longestlength:= 1 Position:= 11 Calculating Longest Prefixes b/w ana#ananab AND anab The Longest Prefix b/w them is :ana The Length is :longestlength:= 3 Position:=9 Calculating Longest Prefixes b/w anana#ananab AND ananab The Longest Prefix b/w them is :anana The Length is :longestlength:= 5 Position:= 7 So Answer =5. And the Longest Palindrome is :=Str[7,7+5-1]=anana 

    Faites juste une note ::

    La condition if de l’étape 4 fait essentiellement référence au fait que, dans chaque itération (i), si je prends les suffixes s1 (i) et s2 (i-1) alors, “s1 doit contenir # et s2 ne doit pas contenir” must contient # et s1 ne doit pas contenir # “.

      |(1:BANANA#ANANAB)|leaf tree:| | | | |(7:#ANANAB)|leaf | | |(5:NA)| | | | |(13:B)|leaf | |(3:NA)| | | |(7:#ANANAB)|leaf | | | | | |(13:B)|leaf |(2:A)| | |(7:#ANANAB)|leaf | | | |(13:B)|leaf | | | |(7:#ANANAB)|leaf | |(5:NA)| | | |(13:B)|leaf |(3:NA)| | |(7:#ANANAB)|leaf | | | |(13:B)|leaf | |(7:#ANANAB)|leaf 

    Quelques années de retard …

    Supposons que s soit la chaîne d’origine et que r soit inversé. Supposons également que nous avons complètement construit un arbre de suffixe ST utilisant s .

    Notre prochaine étape consiste à vérifier tous les suffixes de r contre ST . Avec chaque nouveau suffixe de r , nous tiendrons compte des k premiers caractères que nous avons comparés avec succès par rapport à un suffixe préexistant dans l’arbre (c’est-à-dire l’un des suffixes de s).

    Par exemple, disons que nous faisons correspondre le suffixe “RAT” de r , et que s contenait des suffixes commençant par “RA” , mais aucun ne correspondait à “RAT” . k serait égal à 2 quand nous avons finalement dû abandonner l’espoir pour les derniers caractères “T” . Nous avons comparé les deux premiers caractères du suffixe de r avec les deux premiers caractères du suffixe de s. Nous appellerons ce noeud que nous avons atteint n .

    Maintenant, comment soaps-nous quand nous avons trouvé un palindrome? En vérifiant tous les nœuds feuilles sous n .

    Dans une arborescence de suffixes traditionnelle, l’index de départ de chaque suffixe est stocké au nœud feuille de cette twig de suffixe. Dans notre exemple ci-dessus, s peut contenir un tas de suffixes commençant par “RA” , chacun commençant à l’un des index présents dans les descendants du noeud feuille de n .

    Utilisons ces indices.

    Qu’est-ce que cela signifie si nous comparons k caractères d’une des sous-chaînes de R avec k caractères dans ST ? Eh bien, cela signifie simplement que nous avons trouvé des chaînes inversées. Mais qu’est-ce que cela signifie si l’emplacement où la sous-chaîne commence dans R est égal à la sous-chaîne correspondante dans S plus k ? Oui, cela signifie que s[i] through s[i+k] lit la même chose que s[i+k] through s[i] ! Et donc, soit la définition, nous avons localisé un palindrome de taille k .

    Maintenant, tout ce que vous avez à faire est de garder un onglet sur le palindrome le plus long trouvé à ce jour et de le retourner à la fin de votre fonction.

    Explication simple et courte de Skiena - The Algorithm Design Manual

    Trouver le plus long palindrome dans S [en utilisant l’arbre des suffixes] – Un palindrome est une chaîne qui lit la même chose si l’ordre des caractères est inversé, par exemple madam . Pour trouver le plus long palindrome d’une chaîne S, construisez un arbre de suffixe unique contenant tous les suffixes de S et l’inversion de S, chaque feuille étant identifiée par sa position de départ. Un palindrome est défini par n’importe quel nœud de cet arbre qui a des enfants avant et arrière de la même position.

    Solution DP:

     int longestPalin(char *str) { n = strlen(str); bool table[n][n]l memset(table, 0, sizeof(table)); int start = 0; for(int i=0; i maxlen) { start = i; maxlen = k; } } } } print(str, start, start+maxlen-1); return maxlen; }