参考网站
代码
#include
#include
using namespace std;
int next[101];
void getNext(string str){ // 获取前缀表部分
string tmp = "";
int cnt = 0;
next[0] = -1; // 第一个元素对应的前缀为-1
for(int i = 0; i < str.length(); i++){
tmp += str[i]; // 每次加一个元素
// 把第cnt个元素和最后一个元素对比
if(tmp[cnt] != tmp[i]) // 不同时cnt初始化为0
cnt = 0;
if(tmp[cnt] == tmp[i] && i != 0) // 相同时cnt++,用于下一次判断
cnt++;
next[i+1] = cnt; // 每个元素前缀的值为cnt的值
}
}
int kmp(string t, string p){ // 字符串比较部分
getNext(p);
int i = 0, j = 0; // i为原文的下标,j为需要匹配的字符串下标
while(i < t.length() && j < p.length()){ // 边界
if(j == 0 || t[i] == p[j]){ // 当前前缀的值为0或者两个元素相等时,继续
i++;
j++;
}
else // 匹配失败,根据前缀表继续跳转
j = next[j];
}
if(j == p.length()) // 当全部匹配时返回
return i - j; // 返回匹配到的位置
return -1;
}
int main(){
string t = "bbc abcdab abcdabcdabde";
string p = "abcdabd";
cout << kmp(t, p) << endl;
}
Comments | NOTHING