2
J'ai un ensemble de chaînes, et j'ai besoin de construire un graphe où les chaînes sont les nœuds, et il y a un bord entre une paire de adjacentes chaînes.Construire le graphique des chaînes "adjacentes"
Pour les chaînes A et B sont dit être à côté si en ajoutant, supprimant, ou le remplacement d'un seul caractère de A (quel que soit la position), vous obtenez B.
Par exemple scar et car sont adjacentes (en enlevant la s de scar), sont donc car et far (remplaçant c avec f) et sont donc far et farm (ajout m).
Est-il possible de le faire en moins de O(n^2)?
Comme la distance d'édition est une distance, la l'inégalité triangulaire tient. Je pense que dans le cas général vous pouvez partitionner l'espace en gardant récursivement les sous-ensembles avec la distance <= 2 au dernier point examiné comme candidats, et les rejeter pour calculer les autres éléments de l'AM. Dans le pire des cas, tous les éléments resteront dans le même sous-ensemble pour toujours. –
C'est le point de mon exemple graphique complet. C'est le pire des cas. – jason
Le graphique ne doit pas être stocké en tant que matrice d'adjacence. – Nabb