• 发表于 4年前
• 阅读 78
• 收藏 0
• 评论 0

1.关于本文

2.方法1：朴素的字符串搜索算法

``````#include<iostream>
#include<string>

using namespace std;

//函数：找出字符串s中第一次出现字符串a的位置（朴素算法）
int IndexOf_01(string s,string a)
{
bool isMatch;
for(int i = 0; i <= s.length() - a.length(); i++)
{
isMatch = true;
for(int j = 0; j < a.length(); j++)
{
if(s[i + j] != a[j])
{
isMatch = false;
break;
}
}

if(isMatch)
{
return i;
}
}

return -1;
}

int main()
{
string s = "the quick brown fox jumped over the lazy dogs";

cout << s << endl;
cout << "index of \"the\": " << IndexOf_01(s, "the") << endl;
cout << "index of \"quick\": " << IndexOf_01(s, "quick") << endl;
cout << "index of \"dogs\": " << IndexOf_01(s, "dogs") << endl;
cout << "index of \"cats\": " << IndexOf_01(s, "cats") << endl;

return 0;
}``````

3.方法2

``````#include<iostream>
#include<string>

using namespace std;

//函数：找出字符串s中第一次出现字符串a的位置（受到Rabin-Karp算法启发）
int IndexOf_02(string s,string a)
{
//s的长度应大于a的长度
if(s.length() < a.length())
{
return -1;
}

//计算第一组数字和
int target = 0, current = 0;
for(int i = 0; i < a.length(); i++)
{
target += a[i];
current += s[i];
}

//开始匹配
bool isMatch;
for(int i = 0; i <= s.length() - a.length(); )
{
//如果所有字符的数字和相同，则进一步比较
if(current == target)
{
isMatch = true;
for(int j = 0; j < a.length(); j++)
{
if(s[i + j] != a[j])
{
isMatch = false;
break;
}
}

if(isMatch)
{
return i;
}
}

//计算下一组字符的数字和
current -= s[i];
current += s[i++ + a.length()];
}

return -1;
}

int main()
{
string s = "the quick brown fox jumped over the lazy dogs";

cout << s << endl;
cout << "index of \"the\": " << IndexOf_02(s, "the") << endl;
cout << "index of \"quick\": " << IndexOf_02(s, "quick") << endl;
cout << "index of \"dogs\": " << IndexOf_02(s, "dogs") << endl;
cout << "index of \"cats\": " << IndexOf_02(s, "cats") << endl;

return 0;
}``````

4.Knuth-Morris-Pratt（KMP）算法

KMP算法，函数ComputePrefix用于计算辅助数组

``````#include<iostream>
#include<string>

using namespace std;

//计算前缀
int* ComputePrefix(string a)
{
int *array = new int[a.length() + 1];

int x = 0;
array[0] = 0;
for(int i = 1; i < a.length(); i++)
{
if(a[i] == a[x])
{
array[i] = array[i - 1] + 1;
x++;
}
else
{
array[i] = 0;
x = 0;
}
}

return array;
}

//函数：找出字符串s中第一次出现字符串a的位置（KMP算法）
int IndexOf_KMP(string s, string a)
{
//计算前缀
int *perfix = new int[a.length()];
perfix = ComputePrefix(a);

//判断a在s中第一次出现的位置
int x = 0, y = 0;
while(x < s.length())
{
if(s[x + y] == a[y])
{
y++;
if(y == a.length())
{
return x;
}
}
else
{
if(y == 0)
{
x++;
}
else
{
x += (y - perfix[y - 1]);
}
y = 0;
}
}

return -1;
}

int main()
{
string tests = "ababaabababcabab";
cout << tests << endl;

string testa0 = "ababa";
cout << testa0 << ": " << IndexOf_KMP(tests, testa0) << endl;

string testa1 = "ababc";
cout << testa1 << ": "  << IndexOf_KMP(tests, testa1) << endl;

string testa2 = "cabab";
cout << testa2 << ": " << IndexOf_KMP(tests, testa2) << endl;

string testa3 = "aaaaa";
cout << testa3 << ": " << IndexOf_KMP(tests, testa3) << endl;

return 0;
}``````

×