Le plus long palindrome d'une chaîne utilisant un arbre de suffixe

Question

J'essayais de trouver le plus long palindrome d'une chaîne. La solution de force brute prend O (n ^ 3) temps. J'ai lu qu'il existe un algorithme temporel linéaire utilisant des arbres de suffixes. Je connais les arbres à suffixes et je suis à l'aise pour les construire. Comment utilisez-vous l'arbre de suffixe construit pour trouver le plus long palindrome.

Answer 1

Le Linéaire de la solution peut être trouvée dans cette Voie ::

Prequisities:

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

(2).Vous devez savoir comment trouver le standard LCP Tableau ie. LCP entre les Suffixes i et i-1

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

Let' S être la Chaîne d'Origine et de S' être le revers de la Chaîne d'Origine. Permet de prendre S="banane" comme un exemple. Alors son Inverse string S'=ananab.

Étape 1: Concaténer S + # + S" pour obtenir la Chaîne de caractères Str ,où # est un alphabet non présents dans la Chaîne d'origine.

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

Étape 2: Maintenant construire le Suffixe Tableau de la chaîne Str.

Dans cet exemple ,le suffixe tableau 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 suffixe tableau est un tableau d'entiers donnant les positions de départ des suffixes d'une chaîne de caractères dans l'ordre lexicographique.Ainsi, le Tableau qui contient l'Index de la position de départ est un suffixe de Tableau.

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

Étape 3: Comme vous l'aviez réussi à construire le Suffixe Tableau ,Maintenant trouver de la plus Longue Préfixes Communs Entre les adjacente suffixes.

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, LCP tableau LCP={0,0,1,1,3,3,5,0,1,0,2,2,4}.

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

Étape 4:

Maintenant que vous avez construit un LCP ,tableau, Utilisez la Logique suivante.

    Let the length of the Longest Palindrome ,longestlength:=0 (Initially)
    Let Position:=0.
    for(int i=1;i<Len;++i)
    {
        //Note that Len=Length of Original String +"#"+ Reverse String
        if((LCP[i]>longestlength))
        {
            //Note Actual Len=Length of original Input string .
            if((suffixArray[i-1]<actuallen && suffixArray[i]>actuallen)||(suffixArray[i]<actuallen && suffixArray[i-1]>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];

L'Exécution Exemple ::

    actuallen=Length of banana:=6
    Len=Length of "banana#ananab" :=13.

Calculating Longest Prefixes b/w a#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

Il suffit de Faire une Remarque:

La condition si à l'Étape 4, fondamentalement, fait référence ,à chaque itération(i) ,si je prends les suffixes s1(i) et s2(i-1), puis, "s1 doivent contient # et s2 ne doit pas contenir #" OU "s2 ne contient # et s1 ne doit pas contient # ".

 |(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

Answer 2

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

Laissez - y₁y₂ ... y_n être votre chaîne (où y_i sont des lettres).

Créer la généralisation d'un suffixe arbre de S_f = y₁y₂ ... y_n$ et S_r = y_ny_{n - 1} ... y₁# (inverse les lettres et choisissez les différents caractères de fin de S_f ($) et S_r (#))... où S_f signifie "Chaîne de caractères, De l'avant" et S_r signifie "Chaîne, Reverse".

Pour chaque suffixe i dans S_f, trouve le plus petit ancêtre commun avec le suffixe n - i + 1 dans S_r.

Ce qui s'exécute à partir de la racine jusqu'à ce plus petit commun ancêtre est un palindrome, parce que maintenant, le plus bas de l'ancêtre commun représente le plus long préfixe commun de ces deux suffixes. Rappelons que:

(1) Un préfixe, un suffixe est un sous-chaîne.

(2) Un palindrome est une chaîne identique à celle de son inverse.

(3) Ainsi, la plus longue contenues palindrome au sein d'une chaîne est exactement la plus longue sous-chaîne commune de cette chaîne et son inverse.

(4) Ainsi, la plus longue contenues palindrome au sein d'une chaîne est exactement la plus longue de la commune préfixe 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#

Ci-dessous est généralisé suffixe arbre de S_f et S_r, où le nombre à la fin de chaque chemin est l'indice correspondant au suffixe. Il y a une petite erreur, l' un commun à tous les 3 branches de Blue_4 du parent doit être sur son entrée de bord, à côté de n:

Le plus bas de l'intérieur nœud de l'arbre est la plus longue sous-chaîne commune de cette chaîne et son inverse. En regardant tout l'intérieur des nœuds dans l'arbre vous permettra donc de trouver le plus long palindrome.

Le plus long palindrome est trouvé entre les entre les Green_0 et Blue_1 (c'est à dire, de la banane et anana) et est anana

---

MODIFIER

Je viens de trouver ce document qui répond à cette question.

Answer 3

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<n; ++i)
        table[i][i] = true;
    int maxlen = 1;

    for(int i=0; i<n-1; ++i)
    {
        if(str[i] == str[i+1])
        {
            table[i][i] = true;
            start = i;
            maxlen = 2;
        }
    }

    for(int k=3; k<=n; ++k)
    {
        for(int i=0; i<n-k+1; ++i)
        {
            int j = n+k-1;
            if(str[i] == str[j] && table[i+1][j-1])
            {
                table[i][j] = true;
                if(k > maxlen)
                {
                    start = i;
                    maxlen = k;
                }
            }
        }
    }
    print(str, start, start+maxlen-1);
    return maxlen;
}