KMP 算法实例详解
KMP 算法实例详解
KMP算法,是由Knuth,Morris,Pratt共同提出的模式匹配算法,其对于任何模式和目标序列,都可以在线性时间内完成匹配查找,而不会发生退化,是一个非常优秀的模式匹配算法。
分析:KMP模板题、KMP的关键是求出next的值、先预处理出next的值、然后一遍扫过、复杂度O(m+n)
实例代码:
#include<stdio.h> #include<string.h> #define N 1000005 int s[N]; int p[N]; int next[N]; int m,n; void getnext(){ int j=0,k=-1; next[0]=-1; while(j<m){ if(k==-1||p[j]==p[k]){ j++; k++; next[j]=k; } else k=next[k]; } } int kmp(){ int i=0,j=0; getnext(); while(i<n){ if(j==-1||s[i]==p[j]){ i++; j++; } else j=next[j]; if(j==m) return i; } return -1; } int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",&s[i]); for(int i=0;i<m;i++) scanf("%d",&p[i]); if(kmp()==-1) printf("-1\n"); else printf("%d\n",kmp()-m+1); } return 0; }
以上就是KMP 算法的实例详解本站关于数据结构和算法的文章还有很多,希望大家搜索查阅,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
上一篇:浅谈C++ Socket编程
栏 目:C语言
下一篇:C语言实现2048游戏
本文标题:KMP 算法实例详解
本文地址:https://www.xiuzhanwang.com/a1/Cyuyan/1313.html
您可能感兴趣的文章
- 01-10使用C++实现全排列算法的方法详解
- 01-10深入第K大数问题以及算法概要的详解
- 01-10深入N皇后问题的两个最高效算法的详解
- 01-10用C++实现DBSCAN聚类算法
- 01-10深入全排列算法及其实现方法
- 01-10全排列算法的非递归实现与递归实现的方法(C++)
- 01-10贪心算法 WOODEN STICKS 实例代码
- 01-10输出1000以内的素数的算法(实例代码)
- 01-10使用map实现单词转换的实例分析
- 01-10快速模式匹配算法(KMP)的深入理解
阅读排行
本栏相关
- 04-02c语言函数调用后清空内存 c语言调用
- 04-02func函数+在C语言 func函数在c语言中
- 04-02c语言的正则匹配函数 c语言正则表达
- 04-02c语言用函数写分段 用c语言表示分段
- 04-02c语言中对数函数的表达式 c语言中对
- 04-02c语言编写函数冒泡排序 c语言冒泡排
- 04-02c语言没有round函数 round c语言
- 04-02c语言分段函数怎么求 用c语言求分段
- 04-02C语言中怎么打出三角函数 c语言中怎
- 04-02c语言调用函数求fibo C语言调用函数求
随机阅读
- 08-05dedecms(织梦)副栏目数量限制代码修改
- 08-05织梦dedecms什么时候用栏目交叉功能?
- 01-10SublimeText编译C开发环境设置
- 08-05DEDE织梦data目录下的sessions文件夹有什
- 01-11ajax实现页面的局部加载
- 01-11Mac OSX 打开原生自带读写NTFS功能(图文
- 01-10使用C语言求解扑克牌的顺子及n个骰子
- 01-10delphi制作wav文件的方法
- 01-10C#中split用法实例总结
- 04-02jquery与jsp,用jquery