Le plus long préfixe commun de n de chaîne
Donné n de chaîne de longueur max. m. Comment pouvons-nous trouver le plus long préfixe commun partagé par au moins deux chaînes d'entre eux?
Exemple: ['fleur', 'flux', 'bonjour', 'flotte']
Réponse: fl
Je pensais à la construction d'un Trie pour l'ensemble de la chaîne, puis en cochant la plus profonde nœud (satisfait plus longue) qui se ramifie à deux ou plusieurs sous-chaînes (satisfait de points communs). Cela prend un temps O(n*m) le temps et l'espace. Est-il une meilleure façon de le faire
Je crois que cet exemple serait
une chaîne peut démarrer sans 'fl'. 'bonjour' a été mis à prouver un point qu'il pourrait être toutes les chaînes où dans la chaîne de 1 n'ont pas besoin de tout préfixe commun avec les autres
flow
. À en juger par le contexte de la solution proposée, il n'a qu'à être commune au moins à 2, pas à tous. Je suis d'accord quelques précisions de l'OP est nécessaire ici.une chaîne peut démarrer sans 'fl'. 'bonjour' a été mis à prouver un point qu'il pourrait être toutes les chaînes où dans la chaîne de 1 n'ont pas besoin de tout préfixe commun avec les autres
OriginalL'auteur shreyasva | 2011-12-20
Vous devez vous connecter pour publier un commentaire.
Pourquoi utiliser trie(qui prend O(mn) en temps et O(mn) de l'espace, il suffit d'utiliser la base de la force brute. première boucle, trouver la plus courte chaîne de caractères comme minStr, qui prend o(n) l'heure, la seconde boucle, comparer un par un avec cette minStr, et de garder une variable qui indique le plus à droite de l'indice de minStr, cette boucle prend O(mn) où m est la longueur la plus courte de toutes les chaînes. Le code est comme ci-dessous,
OriginalL'auteur Charlie Ma
il y a un
O(|S|*n)
solution à ce problème, à l'aide d'un trie. [n
est le nombre de cordes,S
est la chaîne la plus longue]Il n'est pas possible solution plus rapide puis il [en termes de notation grand O], dans le pire des cas, toutes vos chaînes sont identiques - et vous avez besoin de tous les lire pour le savoir.
actualisez votre page, j'ai ajouté une phrase expliquant pourquoi ce problème est
Omega(n*m)
, si aucune solution ne peut faire mieux alorsO(n*m)
Je ne comprenais pas le DFS solution. Pouvez-vous donner un exemple?
ne peut-on pas aller de gauche à droite de vérifier si le caractère à la position X est le même pour toutes les chaînes, retirez la ficelle pour qui ce n'est pas remplie et itérer jusqu'à ce que nous allons à la fin de la plus courte chaîne ou nous avons seulement 1 chaîne dans notre tableau de chaînes de caractères. Nous avons juste besoin de se rappeler le dernier plus long préfixe. Complexité en même temps, mais pas besoin d'un trie.
OriginalL'auteur amit
Je voudrais de les trier, de ce que vous pouvez faire dans
n lg n
temps. Ensuite, toutes les chaînes de caractères communs avec les préfixes sera juste à côté de l'autre. En fait, vous devriez être en mesure de garder un pointeur d'index que vous êtes en train de regarder et de travailler votre chemin vers le bas pour un joli rapide calcul.en fait il fait il
O(m*nlog(n))
et pasO(nmlog(nm))
, parce que, comme vous l'avez dit: comparaison prendO(m)
, et il y aO(nlogn)
de personnes, le total desO(mnlog(n))
Dans le pire des cas, oui, c'est vrai. Cependant que le pire des cas s'applique uniquement lorsque les chaînes elles-mêmes sont très, très similaires, ce qui signifie qu'il y aurait beaucoup moins de permutation. Je n'ai pas fait le calcul sur elle, et il est concevable qu'un artificiel cas serait la cause à se dégrader, mais il semble toujours comme la meilleure option, surtout compte tenu de l'espace.
Aussi, la notion de
m
est important quandm
est sensiblement proche de ou supérieure àn
. Un typiquem
sera de 12 ou moins pour les mots anglais standard, et si nous considérons non-inventé, non-mots techniques, nous sommes à la recherche à 33 (antidisestablishmentarianistically). Elle a donc un impact si votren
est, disons, 100 ou moins, mais si c'est le cas de votre ensemble de l'opération est de petite taille etO
ne s'applique pas.O
notation asymptotique pour l'évaluation.OriginalL'auteur corsiKa
Comme une réponse complètement différente de mes autres réponses...
Vous pouvez, avec un seul passage, un seau à chaque chaîne de caractères en fonction de sa première lettre.
Avec un autre pass, vous pouvez trier chaque compartiment basé sur sa seconde plus tard. (Ceci est connu comme radix, ce qui est
O(n*m)
, etO(n)
à chaque passage.) Cela vous donne une base de référence préfixe de 2.Vous pouvez supprimer en toute sécurité à partir de votre jeu de données tous les éléments qui n'ont pas de préfixe de 2.
Vous pouvez continuer la base de tri, suppression des éléments sans partagée préfixe de
p
, commep
approchesm
.Cela vous donnera la même
O(n*m)
temps que le trie approche, mais ce sera toujours plus rapide que la trie depuis la trie doivent examiner chaque caractère de chaque chaîne (comme il entre dans la structure), bien que cette approche n'est garantie qu'à regarder les 2 caractères par chaîne, à quel point il saisit une grande partie de l'ensemble de données.Le pire des cas est toujours que chaque chaîne est identique, c'est pourquoi il partage la même notation grand O, mais sera plus rapide dans tous les cas, comme il est garanti à utiliser le moins de se livrer à quelques comparaisons sur les "non-pire-cas" il y a des personnages qui n'ont jamais besoin d'être visité.
OriginalL'auteur corsiKa
OriginalL'auteur user3053120
Il arrive que le seau de tri (tri radix), décrit par corsiKa peut être prolongé de manière à ce que toutes les chaînes sont finalement placé seul dans un seau, et à ce point, LCP pour un solitaire de la chaîne est connue. De plus, le shustring de chaque chaîne est également connue; elle est un temps plus long que le LCP. Le seau de tri est de facto la construction d'un suffixe tableau, mais seulement partiellement. Ces comparaisons qui ne sont pas réalisés (comme décrit par corsiKa) représentent les parties du suffixe chaînes qui ne sont pas ajouté le suffixe tableau. Enfin, cette méthode permet de déterminer non seulement le LCP et shustrings, mais aussi l'on peut facilement trouver ces sous-séquences qui ne sont pas présents au sein de la chaîne.
OriginalL'auteur wrb
Depuis que le monde est évidemment la mendicité pour une réponse rapide, voici le mien 😉
Swift 3 Mise À Jour:
Ce qui est intéressant à noter:
est la longueur d'un plus court chemin.
Grapheme Clusters
qui leCharacter
type représente.Et compte tenu de la fonction que j'ai besoin d'écrire à la première place:
ici est une unité minimale de test:
OriginalL'auteur verec