关注
#include <iostream>
#include <string>
using namespace std;
int b_force_match(string str, string ptr)
{
int i, j, temc;
int tlen = ptr.length();
int plen = str.length();
for (i = 0, j = 0; i <= plen - tlen; i++)
{
temc = i;
j = 0;
while (str[temc] == ptr[j] && j < tlen)
{
temc++;
j++;
}
if (j == tlen)
return i;
}
return -1;
}
void clnext(string str, int *next)
{
int len=str.length();
next[0] = -1;
int k = -1;
for (int q = 1; q < len; q++)
{
while (k > -1 && str[k + 1] != str[q])
k = next[k];//回溯
if (str[k + 1] == str[q])
k++;
next[q] = k;
}
}
int KMP(string str,string ptr)
{
int slen=str.length();
int plen=ptr.length();
int *next = new int[plen];
clnext(ptr, next);
int k = -1;
for (int i = 0; i < slen; i++)
{
while (k >-1&& ptr[k + 1] != str[i])
k = next[k];
if (ptr[k + 1] == str[i])
k = k + 1;
if (k == plen-1)
{
delete next;
return i-plen+1;
}
}
delete next;
return -1;
}
int main()
{
string str = "ahraaahahafafderqhgadgdfghadfhnmym,,aryzkiababaabaftyacfabaou";
string ptr = "ababaabaf";
cout << "patternmatch" << endl;
cout << "b_force:" << endl;
cout << b_force_match(str, ptr) << endl;
cout<<"KMP:"<<endl;
cout << KMP(str, ptr) << endl;
return 0;
}
查看原帖
点赞 评论
相关推荐
10-17 16:03
腾讯_PCG_后台开发(实习员工) 点赞 评论 收藏
分享
牛客热帖
正在热议
# 同bg的你秋招战况如何? #
17765次浏览 143人参与
# 写简历别走弯路 #
580004次浏览 7192人参与
# 0offer互助地 #
120430次浏览 1230人参与
# 你的简历改到第几版了 #
641633次浏览 9443人参与
# 我的简历长这样 #
1632051次浏览 25633人参与
# 寒假躺平还是提前实习 #
21579次浏览 91人参与
# 你会为了工作牺牲生活吗? #
18038次浏览 159人参与
# 国企vs私企,你更想去? #
77198次浏览 942人参与
# 如何写一份好简历 #
553576次浏览 8040人参与
# 第一份工作应该只看薪资吗 #
45031次浏览 813人参与
# 最后再改一次简历 #
1708755次浏览 27267人参与
# 正在实习的碎碎念 #
1173004次浏览 12438人参与
# 实习与准备秋招该如何平衡 #
600254次浏览 7432人参与
# 工作两年想退休了 #
43399次浏览 551人参与
# 你们的毕业论文什么进度了 #
762116次浏览 7655人参与
# 非技术岗薪资爆料 #
135259次浏览 1239人参与
# 蚂蚁求职进展汇总 #
13403次浏览 185人参与
# 工作压力大怎么缓解 #
29676次浏览 444人参与
# offer帮选 #
211037次浏览 2158人参与
# 能让你振作起来的一句话 #
32817次浏览 329人参与