Étant donné n chaînes, l'une d'elles est-elle une sous-chaîne d'une autre?

Supposons que l'on nous donne une collection de chaînes, . Je voudrais savoir si l'une de ces chaînes est une sous-chaîne d'une autre chaîne de la collection. En d'autres termes, j'aimerais un algorithme pour la tâche suivante: $n$ $S_1,\dots,S_n$

Entrée: $S_1,\dots,S_n$

Sortie: telle que est une sous-chaîne de et , ou None si aucune telle n'existe $i,j$ $S_i$ $S_j$ $i\ne j$ $i,j$

Existe-t-il un algorithme efficace pour cela?

Si nous remplaçons «sous-chaîne» par «préfixe», il existe un algorithme efficace (triez les chaînes, puis effectuez un balayage linéaire pour comparer les chaînes adjacentes; le tri garantira que les sous-chaînes sont adjacentes). Mais il semble plus difficile de tester si une chaîne est une sous-chaîne d'une autre chaîne. Un algorithme naïf consiste à parcourir toutes les paires , mais cela nécessite des tests de sous-chaîne . Existe-t-il un algorithme plus efficace? $i,j$ $\Theta(n^2)$

Je suppose que nous pourrions appeler cela "test de sous-chaîne toutes paires", ou quelque chose comme ça.

Mon but ultime est d'élaguer la collection afin qu'aucune chaîne ne soit une sous-chaîne d'une autre, en supprimant chacune qui est une sous-chaîne de quelque chose d'autre dans la collection.

Astuce: tableau de suffixes.

Pseudonyme du

En remarque,

n'est pas correct si vous supprimez les sous-chaînes au fur et à mesure que vous les trouvez. Ce sera moins. En outre, vous devez trier par longueur car une chaîne plus longue ne peut pas apparaître dans une chaîne plus courte. Encore une fois,

tort ici.

Θ (n^{2})

$\Theta(n^2)$

Θ (n^{2})

$\Theta(n^2)$

Alexis Wilke

@AlexisWilke,

est correct: c'est le nombre de tests de sous-chaîne dans le pire des cas (le pire des cas est lorsqu'aucune chaîne n'est une sous-chaîne d'un autre). Le tri par longueur ne vous donne qu'un facteur de deux, ce qui n'affecte pas les asymptotiques.

Θ (n^{2})

$\Theta(n^2)$

Réponses:

Vous pouvez créer un arbre de suffixes en temps linéaire et vérifier s'il y a un nœud interne qui correspond à une chaîne complète (temps constant par nœud).

Plus en détail, supposons que l'on nous donne des chaînes . $s_1, \dots, s_n \in \Sigma^*$

Construisez un arbre de suffixes (généralisé) de avec marqueurs de terminal distincts par paire . $s_1\$_1, s_2\$_2, \dots, s_n\$_n$ $n$ $\$_1,\dots,\$_n \notin \Sigma$

En utilisant l'algorithme d'Ukkonen , cela peut être fait en temps linéaire; linéaire dans la somme de toutes les longueurs de chaîne.
$(i,j)$ $s_i[j..|s_i|]$ $s_i$ $n$ $(i,0)$

Cela prend du temps linéaire dans la taille de l'arbre, qui lui-même est linéaire dans la taille d'entrée.
$(i,0)$ $\$_i$ $(i,0)$

Cela prend à nouveau du temps linéaire.

Les marqueurs terminaux distincts ne sont pas vraiment nécessaires; une seule utilisée pour terminer toutes les chaînes est tout à fait suffisante tant que vous autorisez plusieurs étiquettes par feuille.

Raphael
la source