Je me demandais comment compter le nombre d'occurrences de chaque aiguille dans une meule de foin en temps linéaire. Je pensais utiliser l'algorithme Aho-Corasick mais je ne veux pas que la complexité du temps dépende du nombre d'occurrences des aiguilles.Le nombre d'occurrences de sous-chaînes dans une chaîne dans O (N)
Utilisez Rabin–Karp si vous souhaitez rechercher un ensemble de chaînes et n'aimez pas dépendre du nombre d'occurrences. Son temps moyen/meilleur cas est O(n + m), mais son temps le plus défavorable est O (nm), où n est la longueur du texte et m est la longueur combinée des motifs de recherche.
Si vous souhaitez rechercher une seule chaîne que vous pouvez utiliser Knuth–Morris–Pratt avec la complexité O(n + k), où n est la longueur du texte et k est la longueur du modèle de recherche.
Si vous n'avez besoin que du nombre total d'occurrences (et que vous ne vous souciez pas des positions elles-mêmes), vous pouvez utiliser Aho-Corasick efficacement. Supposons que nous sommes actuellement dans le noeud v. Combien de sous-chaînes se terminent dans la position actuelle. Je prétends que c'est exactement le nombre de nœuds terminaux accessibles à partir de v par des liens de suffixe. Mais les liens suffixes forment un arbre. Ainsi, nous devons compter le nombre de sommets terminaux sur le chemin de v à la racine dans l'arbre formé par des liens de suffixe. Nous pouvons le faire en O(1) avec un pré-traitement linéaire (par exemple, on peut construire explicitement cet arbre et calculer la somme sur le chemin de la racine à n'importe quel sommet en temps linéaire en utilisant une recherche en profondeur). Nous pouvons également traiter les sommets dans le bon ordre (par exemple, dans l'ordre croissant de hauteur) et faire quelque chose comme sum[v] += sum[suffix_link(v)]. Dans ce cas, nous n'avons même pas besoin de construire réellement cet arbre.
Cet algorithme fonctionne clairement en temps linéaire dans la taille de l'entrée (nous construisons l'automate Aho-Corasick et calculons la somme sur les "chemins de lien suffixe" en temps linéaire, puis nous utilisons l'automate comme d'habitude) .
La sous-chaîne est-elle fixe? C'est-à-dire, avez-vous besoin de compter le nombre de fois qu'une chaîne fixe S se produit dans une chaîne fixe T? – kraskevich
C'était mon erreur, c'était pour plusieurs aiguilles, maintenant ça devrait être correct. – mathew7k5b