trouver la plus longue sous-séquence similaire dans une chaîne

Supposons que je souhaite trouver la sous-séquence la plus longue de sorte que la première moitié de la sous-séquence soit la même que la seconde moitié.trouver la plus longue sous-séquence similaire dans une chaîne

Par exemple: Dans une chaîne abkcjadfbck, le résultat est abcabc car abc est répété dans la première et la seconde moitié de celui-ci. Dans un aaa, le résultat est aa.

Source

2012-04-01 test

Je ne comprends pas. Où est 'abc' n'importe où dans la première chaîne? Et pourquoi le résultat de la deuxième chaîne n'est-il pas 'aaa'? Clairement c'est plus long. –

Je suppose que la sous-séquence ne signifie pas que les indices doivent être consécutifs. Le résultat obtenu est soit [index 0, index 1], [index 1, index 2] ou [index 0, index 2]. – DaveFar

aaa a "aa" résultat parce que dans "aa" la première moitié est la même que la seconde moitié. – test

Cette tâche peut être considérée comme une combinaison de deux problèmes bien connus.

Si vous connaissez à l'avance un point entre deux moitiés de la sous-séquence, il vous suffit de trouver la meilleure correspondance pour deux chaînes. C'est le problème Pairwise alignment. Différentes méthodes de programmation dynamique le résolvent en O (N).
Pour trouver un point où la chaîne doit être divisée de façon optimale, vous pouvez utiliser Golden section search ou Fibonacci search. Ces algorithmes ont une complexité temporelle O (log N).

Source

2012-04-01 19:43:29

Donc, ce que je comprends de notre méthode est que .. à partir de i = 1: n, créer deux chaînes et juste effectuer la plus longue sous-séquence commune sur eux. Donc, ce sera l'ordre de n * (n * n) de trouver la plus longue sous-séquence avec des moitiés similaires. Mais, pouvons-nous générer toutes ces chaînes possibles (pas seulement le plus long)? par exemple, pour aaa, nous aurons 3 de ces chaînes possibles aa, aa, aa. (premier "a" avec deuxième "a", premier "a" avec troisième "a", deuxième "a" avec troisième "a") – test

La recherche de la plus longue sous-séquence avec ces algorithmes est O (N^2 log N) car avec Recherche de section d'or vous n'avez pas besoin de diviser la chaîne sur toutes les positions possibles. Mais cela ne permet pas d'obtenir toutes les sous-séquences. Générer toutes les sous-séquences est une tâche complètement différente et il devrait être résolu par d'autres méthodes. –

Lors d'un premier passage sur inputString, nous pouvons compter la fréquence d'apparition de chaque caractère et supprimer ceux dont l'occurrence est 1.

input: inputString 
data strucutres: 
Set<Triple<char[], Integer, Integer>> potentialSecondWords; 
Map<Char, List<Integer>> lettersList; 

for the characters c with increasing index h in inputString do 
    if (!lettersList.get(c).isEmpty()) { 
    for ((secondWord, currentIndex, maxIndex) in potentialSecondWords) { 
     if (there exists a j in lettersList.get(c) between currentIndex and maxIndex) { 
     update (secondWord, currentIndex, maxIndex) by adding c to secondWord and replacing currentIndex with j; 
     } 
    } 
    if potentialSecondWords contains a triple whose char[] is equal to c, remove it; 
    put new Triple with value (c,lettersList.get(c).get(0), h-1) into potentialSecondWords; 
    } 
    lettersList.get(c).add(h); 
} 
find the largest secondWord in potentialSecondWords and output secondWord twice;

donc cet algorithme passe une fois sur le réseau, ce qui crée pour chaque index, où il est logique, un triple représentant le deuxième mot potentiel à partir de l'indice actuel et met à jour tous les deuxièmes potentiels mots. Avec une implémentation de liste appropriée et n étant la taille de inputString, cet algorithme a l'exécution O dans le cas le plus défavorable (n²), par ex. pour un^n.

Source

2012-04-01 15:30:14 DaveFar

Pouvez-vous s'il vous plaît expliquer l'algo? – test

trouver la plus longue sous-séquence similaire dans une chaîne

Répondre

Questions connexes