Compte tenu d'une liste de chaînes, trouvez chaque paire $ (x, y) $ où $ x $ est une sous-chaîne de $ y $.Possible de faire mieux que $ o (n ^ 2) $?

Question

Considérez le problème algorithmique suivant: donné une liste de chaînes $ l= [s_1, s_2, \ dots, s_n] $ , nous voulons connaître toutes les paires < span class="math-conteneur"> $ (x, y) $ où $ x $ est une sous-chaîne de $ y $ . Nous pouvons supposer que toutes les chaînes sont de longueur au maximum $ M $ , où $ m << n $ et sont tous sur un alphabet fini $ \ sigma $ avec $ | \ sigma | << N $ . Nous pouvons également supposer que le nombre de paires $ (x, y) $ où $ x est un Sous-chaîne de $ Y $ est beaucoup plus petit que $ N $

.

.

Un algorithme trivial serait ceci:

1. foreach x in L:
2.   foreach y in L:
3.      if x is substring of y:
4.         OUTPUT x,y

Cependant, cela a une complexité $ o (n ^ 2 \ cdot m) $ - Je suis curieux de savoir s'il existe un algorithme plus rapide?

modifier : Comme indiqué dans les commentaires, il peut y avoir au plus $ n ^ 2 $ ces paires, donc je ne vois donc pas comment il peut y avoir un algorithme plus rapide que $ O (n ^ 2) $ . Cependant, je me demandais s'il y a quelque chose comme un $ P-FPT $ algorithme où la complexité carrée dépend du nombre de paires de sortie, plutôt que N $ N $ ? Ou au moins un algorithme qui réduit la complexité à quelque chose de mieux que $ O (n ^ 2 \ cdot m) $

.

.

Answer 1

Ceci peut être résolu avec Aho-Corasick Algorithm dans < SPAN CLASSE="MATH-CONTENEUR"> $ O (NM + MM) $ TIME, OU SPAN CLASSE="MATH-CONTENANT"> $ M $ est le nombre de paires sorties.

Construisez d'abord l'automate Aho-Corasick pour l'ensemble des chaînes dans $ O (nm) $ temps. Ensuite, exécutez chaque chaîne via l'automate - cela prend $ O (nm) $ temps pour exécuter les chaînes via l'automate et $ O (mm) $ temps pour la sortie des correspondances car la même chaîne peut correspondre à $ m $ fois dans le pire des cas. (Par exemple, ab correspond à ababab 3 fois.)

---

Ceci peut être amélioré à la vraie linear $ o (l + m) $ heure, où $ l $ est la longueur totale des chaînes et $ m $ est le nombre de correspondances:

Lors de l'exécution des chaînes via l'automate, stockez pour chaque noeud de l'automate l'index de la chaîne précédente pour laquelle ce nœud a été visité. Lors de la sortie des correspondances, arrêtez de suivre les liens de dictionnement si le lien mène à un nœud qui a déjà été visité pour cette chaîne - vous avez déjà émis toutes les correspondances qui sont à la hausse de ce nœud. Maintenant, chaque match est sorti exactement une fois et nous parcourons des liens de dictionnaire que lorsque de nouveaux matchs sont émis.