1.关于本文
本文中所有的代码都为实现一个目标，即：
写一个函数：从字符串s中找到字符串a第一次出现的位置，不存在则返回-1
2.方法1：朴素的字符串搜索算法
用一个循环来找出所有有效位移
#include#include 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
本方法受到了 Rabin-Karp 启发，相当于对原算法做了如下修改
窗口长度：m=a.length()，第一次匹配规则：t=t[0]+t[1]+...+t[t.length()-1]，模p=max
对于字符串s的每一个长度为m的子串，如果该子串所有字符的ASCII码和与目标字符串相同，则逐个比对该子串与目标字符串是否相同，否则跳过。若子串与目标字符串相同，则认为匹配，否则继续向后搜索。
#include#include 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#include 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;}
