第一种方法查找所有出现的字符串在主字符串里的下标：
[cpp]
vector bfSearch(string &text, string &substr)
{
vector begIndex;
int n = text.size();
int m = substr.size();
//注意这里是i<=n-m不是i
for (int i = 0; i <= n - m; i++)
{
int j = 0;
for (; j < m; j++)
{
if (substr[j] != text[i+j])
{
break;
}
}
if (j == m)
{
//注意这里是i，不是i-m
begIndex.push_back(i);
}
}
return begIndex;
}
测试：
[cpp]
int main()
{
string str1 = "abcddbeddbaddb";
string substr = "ddb";
vector vi = bfSearch(str1, substr);
for(auto x:vi)
cout<
cout<
system("pause");
return 0;
}
运行：
显式回溯，查找第一个出现的字符串在主串中的下标：
[cpp]
int bfSearchTrackBack(string &text, string &substr)
{
int n = text.size();
int m = substr.size();
int j = 0;
int i = 0;
for (; i<=n-m && j
{
if (text[i] == substr[j])
{
j++;
}
else
{
i = i-j; //回溯，后面还有i++，所以这里不用+1.
j = 0;
}
}
if (j == m)
return i-m;
return n;
}
测试：
[cpp]
int main()
{
string str1 = "abcddbeddbaddb";
string substr = "ddb";
cout<
system("pause");
return 0;
}