0
J'ai été chargé d'identifier un algorithme efficace [O (n * log (n))] qui, étant donné un ensemble de k Chaînes S = {s-1, s-2, s- 3, ..., sk}, identifiera la plus longue sous-chaîne T pour chaque paire de chaînes (si, sj), telle que T est un suffixe de si et un préfixe de sj, ainsi que la plus longue sous-chaîne T pour chaque paire de cordes (sj, si). n représente les longueurs ajoutées de toutes les k chaînes (n = | s-1 | + | s-2 | + | s-3 | + ... + | s-k |).Algorithme de chevauchement de suffixe-préfixe le plus long
Des pensées? Un lien vers une solution serait bien aussi. Merci d'avance!
La question est vague. la plus longue sous-chaîne du suffixe «Si» et le préfixe «Sj» est l'ensemble de «Si + Sj». Parlons-nous de la plus longue sous-chaîne commune/peu commune? – thebenman
Qu'est ce que le 'n' dans O (log n)? Voulez-vous dire 'k'? Le nombre total de caractères dans toutes les chaînes? Quoi qu'il en soit, le temps logarithmique semble incroyablement optimiste pour un algorithme qui produit des chaînes de résultats k². Avez-vous voulu dire O (n log n)? Précisez s'il vous plaît. – rici
@thebenman: L'objectif est pour la plus longue sous-chaîne qui apparaît dans String Si comme un suffixe AND String Sj comme préfixe. – SupposedlySleeping