我想在一个大字符串中搜索一个字符串的所有位置。
最佳答案
其他两个答案是正确的,但它们非常慢并且具有 O(N^2) 复杂度。但是有 Knuth-Morris-Pratt算法,以 O(N) 的复杂度找到所有子串。
编辑:
此外,还有另一种算法:复杂度为 O(N) 的所谓“Z 函数”,但我找不到该算法的英文来源(可能是因为还有另一个更著名的算法,具有相同的算法) name - 黎曼的 Z 函数),所以我将把它的代码放在这里并解释它的作用。
void calc_z (string &s, vector<int> & z)
{
int len = s.size();
z.resize (len);
int l = 0, r = 0;
for (int i=1; i<len; ++i)
if (z[i-l]+i <= r)
z[i] = z[i-l];
else
{
l = i;
if (i > r) r = i;
for (z[i] = r-i; r<len; ++r, ++z[i])
if (s[r] != s[z[i]])
break;
--r;
}
}
int main()
{
string main_string = "some string where we want to find substring or sub of string or just sub";
string substring = "sub";
string working_string = substring + main_string;
vector<int> z;
calc_z(working_string, z);
//after this z[i] is maximal length of prefix of working_string
//which is equal to string which starting from i-th position of
//working_string. So the positions where z[i] >= substring.size()
//are positions of substrings.
for(int i = substring.size(); i < working_string.size(); ++i)
if(z[i] >=substring.size())
cout << i - substring.size() << endl; //to get position in main_string
}
关于c++ - 如何找到字符串中子字符串的所有位置?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5815838/