KMP，BF，STL之find函数，三种路径，分析如何进行模式串匹配

KMP讲解

PS:这是最好理解的一种

#include
#include
int main()
{char s1[110];char s2[110];printf("请输入两行字符串，分别表示主串和模式串:\n");while(~scanf("%s%s",s1,s2)){int next[110];next[0]=-1;        //由于书上的字符串是以1开头所以next[0]=0,而我是以0开头，所以next[0]=-1,至于为啥，我觉得自己手动算下应该就明白了int i=0;int j=-1;            //重点！！！！！int len1=strlen(s1);int len2=strlen(s2);while(i<len2){if(j==-1||s2[i]==s2[j])     //由于next[0]=-1,所以对j==-1特判下{++i;++j;next[i]=j;}else{j=next[j];}}i=0;j=0;while(i<len1&&j<len2){if(s1[i]==s2[j]||j==-1)    //同样由于next[0]=-1的存在{++i;++j;}else{j=next[j];   //这里就不需要指针回溯，大大降低了时间复杂度}}if(j==len2){printf("%d\n",i-len2+1);}elseprintf("0\n");}return 0;
}

//  KMP算法模式串匹配
#include 
using namespace std;
int main()
{char a[105];char b[1005];memset(a, '\0', sizeof(a));memset(b, '\0', sizeof(b));while (~scanf("%s%s", a, b)){int next[105] = {0};scanf("%s%s", a, b);int i = 1, j = 0;while (i < strlen(a)){if (a[i] == a[j])next[i++] = ++j;else{if (j > 0)j = next[j - 1];elsei++;}}for (int i = 0; i < strlen(a); ++i)printf("%d ", next[i]);printf("\n");i = 0;j = 0;while (i < strlen(b)){if (a[j] == b[i]){++i;++j;if (j == strlen(a)){printf("%d\n", i - j);j = next[j - 1];}}else{if (j > 0)j = next[j - 1];else++i;}}memset(a, '\0', sizeof(a));memset(b, '\0', sizeof(b));}return 0;
}

#include 
using namespace std;
const int cmax = 1e3 + 5;
char str[cmax];
int nex[cmax];
char t[cmax];
void get_next(char T[])
{int i = 1, j = 0, len = strlen(T) - 1;nex[1] = 0;while (i < len){if (j == 0 || T[i] == T[j]){++i;++j;nex[i] = j;}elsej = nex[j];}
}
int Index_KMP(char s[], char t[], int pos)
{int i = pos, j = 1, slen = strlen(s) - 1, tlen = strlen(t) - 1;while (i <= slen && j <= tlen){if (j == 0 || s[i] == t[j]){i++, j++;}elsej = nex[j];}if (j > tlen)return i - tlen;elsereturn 0;
}
int main()
{memset(str, '\0', sizeof(str));memset(nex, 0, sizeof(nex));memset(t, '\0', sizeof(t));scanf("%s%s", t, str);for (int i = strlen(str) - 1; i >= 0; i--)str[i + 1] = str[i];for (int i = strlen(t) - 1; i >= 0; i--)t[i + 1] = t[i];get_next(str);int flag = Index_KMP(t, str, 1);printf("%d\n", flag);memset(nex, 0, sizeof(nex));return 0;
}

//   BF算法模式串匹配
#include 
using namespace std;
int main()
{char a[105];char b[1005];memset(a, '\0', sizeof(a));memset(b, '\0', sizeof(b));while (~scanf("%s%s", a, b)){int alen = strlen(a), blen = strlen(b);int i = 0, j = 0;while (i < blen){if (a[j] == b[i]){++j;++i;if (j == alen){printf("%d\n", i - j);j = 0;i = i - j + 1;}}else{j = 0;i = i - j + 1;}}memset(a, '\0', sizeof(a));memset(b, '\0', sizeof(b));}return 0;
}

//   STL中String的find函数应用
#include 
using namespace std;
int main()
{string a, b;while (cin >> a >> b){int flag = b.find(a);if (flag == -1)printf("NO FOUND\n");else{while (flag != b.npos){printf("%d\n", flag);flag++;flag = b.find(a, flag);}}}return 0;
}

当然，STL肯定比KMP好用。推荐对acm感兴趣的同学可以了解一下STL

对于STL的string不是很懂的同学可以看一下下面的博客：

STL之string函数详解

对于STL感兴趣的同学，可以关注一下这个博主，没错，就是不要脸的我，就是我的博客，我对自己写的东西还是有一丢丢的自信的，对了，我也是一名acm狗，但是我蒟蒻，我愿意和关注我的小伙伴一起进步。

一位蒟蒻的acm狗的博客

Yqifei的博客

如果不想关注，就点个赞吧！毕竟写博客不易，你的支持就是最好的鼓励

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！