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语言kmp算法简单示例和实现原理探究
以前看过kmp算法,当时接触后总感觉好深奥啊,抱着数据结构的数啃了一中午,最终才大致看懂,后来提起kmp也只剩下"奥,它是做模式匹配的"这点干货.最近有空,翻出来算法导论看看,原来就是这么简单(下不说程序实现,思想很简单). 模式匹配的经典应用:从一个字符串中找到模式字串的位置.如"abcdef"中"cde"出现在原串第三个位置.从基础看起 朴素的模式匹配算法 A:abcdefg B:cde 首先B从A的第一位开始比较,B++==A++,如果全
-
快速模式匹配算法(KMP)的深入理解
恐怕现在用过电脑的人,一定都知道大部分带文本编辑功能的软件都有一个快捷键ctrl+f 吧(比如word).这个功能主要来完成"查找","替换"和"全部替换"功能的,其实这就是典型的模式匹配的应用,即在文本文件中查找串.1.模式匹配模式匹配的模型大概是这样的:给定两个字符串变量S和P,其中S成为目标串,其中包含n个字符,P称为模式串,包含m个字符,其中m<=n.从S的给定位置(通常是S的第一个位置)开始搜索模式P.如果找到,则返回模式P在目标
-
C语言中实现KMP算法的实例讲解
一般的算法为什么这么低效呢?那是因为主串指针回溯情况过多: 主串指针如果不回溯的话,速度就会加快,那我们就会想: 如何让主串指针不回溯? KMP算法就是解决了这个问题,所以速度变得更快速了. 它是这样子的: 用一个数组:next[] 求得失配时的位置,然后保存下来. 要说清楚KMP算法,可以从朴素的模式匹配算法说起. 朴素的模式匹配算法比较容易理解,其实现如下 int Index(char s[], char p[], int pos) { int i, j, slen, plen; i =
-
Python字符串匹配算法KMP实例
本文实例讲述了Python字符串匹配算法KMP.分享给大家供大家参考.具体如下: #!/usr/bin/env python #encoding:utf8 def next(pattern): p_len = len(pattern) pos = [-1]*p_len j = -1 for i in range(1, p_len): while j > -1 and pattern[j+1] != pattern[i]: j = pos[j] if pattern[j+1] == pattern
-
KMP算法的C#实现方法
本文实例简述了KMP算法的C#实现方法,分享给大家供大家参考.具体如下: 具体思路为:next函数求出模式串向右滑动位数,再将模式串的str的next函数值 存入数组next. 具体实现代码如下: static void GetNextVal(string str, int [] next) { int i = 0; int j = -1; next[0] = -1; while (i < str.Length - 1) { if (j == -1 || str[i] == str[j]) {
-
字符串的模式匹配详解--BF算法与KMP算法
一.BF算法 BF算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符:若不相等,则比较S的第二个字符和P的第一个字符,依次比较下去,直到得出最后的匹配结果. 举例说明: S: ababcababa P: ababa BF算法匹配的步骤如下 i=0 i=1 i=2 i=3 i=4 第一趟:ababcababa 第二趟:ababcababa 第三趟:ababcababa 第四趟:ababcabab
-
JavaScript中数据结构与算法(五):经典KMP算法
KMP算法和BM算法 KMP是前缀匹配和BM后缀匹配的经典算法,看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同 前缀匹配是指:模式串和母串的比较从左到右,模式串的移动也是从 左到右 后缀匹配是指:模式串和母串的的比较从右到左,模式串的移动从左到右. 通过上一章显而易见BF算法也是属于前缀的算法,不过就非常霸蛮的逐个匹配的效率自然不用提了O(mn),网上蛋疼的KMP是讲解很多,基本都是走的高大上路线看的你也是一头雾水,我试图用自己的理解用最接地气的方式描述 KMP KMP也是一种优化版的
-
C++ 数据结构之kmp算法中的求Next()函数的算法
C++ 数据结构之kmp算法中的求Next()函数的算法 实例代码: #include <iostream> using namespace std; void preKmp(char *c, int m, int Next[]) { int i=1,j=-1; Next[0]=-2; while(i<m) { if(j==-2) { Next[i]=-1; i++; j=-1; } ++j; if(i==m) return; if(c[i]==c[j]) { Next[i]=j; ++
-
java 中模式匹配算法-KMP算法实例详解
java 中模式匹配算法-KMP算法实例详解 朴素模式匹配算法的最大问题就是太低效了.于是三位前辈发表了一种KMP算法,其中三个字母分别是这三个人名的首字母大写. 简单的说,KMP算法的对于主串的当前位置不回溯.也就是说,如果主串某次比较时,当前下标为i,i之前的字符和子串对应的字符匹配,那么不要再像朴素算法那样将主串的下标回溯,比如主串为"abcababcabcabcabcabc",子串为"abcabx".第一次匹配的时候,主串1,2,3,4,5字符都和子串相应的
-
KMP算法精解及其Python版的代码示例
KMP算法是经典的字符串匹配算法,解决从字符串S,查找模式字符串M的问题.算法名称来源于发明者Knuth,Morris,Pratt. 假定从字符串S中查找M,S的长度ls,M的长度lm,且(ls > lm). 朴素的字符串查找方法 从字符串S的第一个字符开始与M进行比较,如果匹配失败.从下一字符开始,重新比较.指导第 (ls - lm) 个字符. 这种方法容易想到并且容易理解,效率不高. 问题在于每次匹配失败后,移动的步伐固定为 1,其实步子可以迈得再大一些. KMP的字符串查找方法 假定在模式
随机推荐
- ThinkPHP文件上传实例教程
- 值得分享的bootstrap table实例
- PHP自动生成表单代码分享
- Yii中CGridView关联表搜索排序方法实例详解
- 原生js实现查询天气小应用
- JavaScript编写带旋转+线条干扰的验证码脚本实例
- CMD命令行下修改网络IP设置的方法
- 编程用到的windows系统目录变量简写
- Linux+php+apache+oracle环境搭建之CentOS下安装Oracle数据库
- 修改Linux主机名的方法
- 不用防火墙自动对付CC攻击防范vbs
- jQuery轻松实现无缝轮播效果
- Android开发系列二之窗口Activity的生命周期
- c#基数排序Radix sort的实现方法
- 中文域名5年内有望赶超英文域名
- python如何使用正则表达式的前向、后向搜索及前向搜索否定模式详解
- Java调用JavaScript实现字符串计算器代码示例
- Linux 强制安装 rpm 包的解决方法
- python3 selenium 切换窗口的几种方法小结
- python基础梳理(一)(推荐)