Possible en double:
substring algorithmtrouver la position d'une chaîne dans une autre chaîne
Étant donné deux chaînes, A et B, comment trouver la première position de B en A? Par exemple, A = "ab123cdefgcde"; B = "cde" Alors la première position de B dans A est 5.
Y at-il un truc pour résoudre ce problème ou simplement chercher A depuis le début?
Le problème que vous résolvez est le problème de "correspondance exacte des chaînes". La solution naïve s'exécute en O (n^2), mais vous pouvez faire beaucoup mieux que cela. Certains algorithmes linéaires pour résoudre ce problème sont Knuth-Morris-Pratt (KMP), Boyer-Moore et Apostolico-Giancarlo. Une autre façon de le résoudre est de construire un automate à états finis qui entre dans un état acceptant lorsqu'il voit la chaîne du motif. La meilleure solution possible est O (n), et tous ceux qui ont le pire temps de fonctionnement. Vous devez scanner la chaîne d'un bout à l'autre; cependant, il est possible de sauter une fraction des caractères (ce que feront Boyer-Moore et Apostolico-Giancarlo), car certaines discordances peuvent impliquer d'autres discordances. Si vous avez besoin de coder vous-même, je vous recommande d'utiliser l'algorithme de Knuth-Morris-Pratt, car il est un peu plus intuitif et plus facile à implémenter que les autres solutions que j'ai mentionnées. La plupart des langages de programmation, cependant, ont une fonction "indexOf" ou "find" qui résoudra cela pour vous.
Vous devez vraiment scanner A dès le départ.
Il existe de bons algorithmes de recherche de sous-chaîne rapide, par ex. http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
Il y a aussi une fonction standard strstr:
strstr(A,B)
Ou 'std :: string :: find' dans le cas de C++. –
La meilleure façon de résoudre ce problème est en utilisant l'algorithme KMP: http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
"Trick" est un autre mot pour algorithme, je suppose. Le plus célèbre est Knuth-Morris-Pratt.
Dans la programmation C vous avez la fonction strstr pour trouver la position de la chaîne de sous dans la source String.
Si vous avez une grande chaîne et vous allez chercher de nombreux sous-chaînes,
il est bon d'avoir à l'esprit la structure suffix array.
Fondamentalement, vous créez un tableau de pointeurs et vous le trier.
Ensuite, vous pouvez localiser n'importe quelle sous-chaîne avec une recherche binaire.
Dupliquer: http://stackoverflow.com/questions/1261041/substring-algorithm – outis