找到一个字符串的位置在另一个字符串

Question

可能重复：
substring algorithm找到一个字符串的位置在另一个字符串

给定两个字符串，A和B，如何找到B在A中的第一位置？例如，A =“ab123cdefgcde”; B =“cde” 那么B在A中的第一个位置是5.

是否有任何技巧可以解决这个问题，或者只是从一开始就搜索A？

Answer 1

您正在解决的问题是“确切的字符串匹配”问题。天真的解决方案运行在O（n^2）时间，但你可以做得比这更好。解决这个问题的一些线性时间算法是Knuth-Morris-Pratt（KMP），Boyer-Moore和Apostolico-Giancarlo。解决它的另一种方法是构造一个有限状态自动机，当它看到模式字符串时进入接受状态。最好的解决方案是O（n），所有这些都有最糟糕的运行时间。你必须从一端扫描字符串到另一端;然而，可以跳过一部分字符（Boyer-Moore和Apostolico-Giancarlo会这样做），因为一些不匹配可能意味着其他不匹配。

如果您需要自己编写代码，我建议您使用Knuth-Morris-Pratt算法，因为它比我提到的其他解决方案更直观，更易于实现。尽管大多数编程语言都有一个“indexOf”或“find”函数，可以为你解决这个问题。

Answer 2

你真的必须从头开始扫描A.

有很好的快速子串搜索算法，例如， http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

还有一个标准功能strstr：

strstr(A,B) 

http://www.cplusplus.com/reference/clibrary/cstring/strstr/

Answer 3

解决这种情况的最佳方式是使用KMP算法：http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

Answer 4

“绝招” 是另一个词算法，我猜。最有名的是Knuth-Morris-Pratt。

Answer 5

见http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

Answer 6

在C编程，有功能的strstr找到源 字符串的子字符串的位置。

Answer 7

如果你有一个大字符串，你要寻找许多子，
这是很好的考虑到有suffix array结构。
基本上，你创建一个指针数组，然后对其进行排序。
然后你可以找到任何二进制搜索的子字符串。