正文

字符串匹配：kmp算法

Vincent_Bryan  Vincent_Bryan  2022-08-09  461

关键词：

一、原理：

　　KMP算法是由Knuth，Morris，Pratt共同提出的模式匹配算法，其对于任何模式和目标序列，都可以在线性时间内完成匹配查找，而不会发生退化，是一个非常优秀的模式匹配算法。朴素算法（即暴力循环）的效率太差，因为它没有好好利用比较时产生的信息，而KMP算法则运用了这一点，所以可以达到更优的复杂度。

　　具体的算法分析可参考：http://www.cnblogs.com/c-cloud/p/3224788.html

二、代码：

 1 /*Sample Input:
 2   abcegfabcd
 3   abc
 4   
 5   Sample Output:
 6   pos: 0
 7   pos: 6
 8 
 9   输入文本串T和模式串P，输出的是所有的匹配成功的位置 
10 */
11 
12 #include<bits/stdc++.h>
13 using namespace std;
14 int next[10010];
15 
16 void getNext(char arr[]){
17     int len = strlen(arr);
18     next[0] = -1;
19     int k = -1;
20     int j = 0;
21     
22     while(j < len){
23         if(k == -1 || arr[j] == arr[k]){
24             j++;
25             k++;
26             next[j] = k;
27         }
28         else{
29             k = next[k];
30         }
31     }
32 }
33 
34 void KMP(char *P, char *T){
35     int Plen = strlen(P);
36     int Tlen = strlen(T);
37     getNext(T);
38     int j = 0;
39     for(int i = 0; i < Tlen; i++){
40         if(T[i] == P[j]){
41             j++;
42         }
43         else{
44             j = next[j];
45             if(j == -1) j = 0;
46             else i--;
47         }
48         
49         if(j == Plen){
50             cout << "pos: " << i - Plen + 1 << endl;
51             j = 0;
52         }
53     }
54 }
55 int main(){
56     char arr1[20];
57     char arr2[5];
58     scanf("%s", arr1);
59     scanf("%s", arr2);
60     KMP(arr2, arr1);
61 }

View Code

三、分析：

1、在对模式串P[m]的处理，即求出next数组的时间花费为O（m）；

2、在进行匹配的时候，近似于对文本串T[n]从头到尾扫一遍，所以时间花费为O（n）；

java数据结构&算法宁可累死自己,也要卷死别人17kmp算法(代码片段)

...&算法的新篇章.KMP算法KMP(Knuth-Morris-Pratt),是一种改进的字符串匹配算法.KMP算法解决了暴力匹配需要高频回退的问题,KMP算法在匹配上若干字符后,字符串位置不需要回退,从而大大提高效率.如图:举个例子(字符串“abcabcdef”匹配... 查看详情

kmp算法

1、概述　　KMP算法是一种改进的字符串匹配算法，关键在于利用匹配失败后的信息，尽量减少模式串与主串的次数。2、算法原理　　举个简单的例子：主串为“BBCABCDABABCDABCDABDE”，匹配串为“ABCDABD” 　　通常我们比较... 查看详情

字符串匹配算法之kmp算法

kmp算法是一种效率非常高的字符串匹配算法，是由Knuth，Morris，Pratt共同提出的模式匹配算法，所以简称KMP算法算法思想在一个字符串中查找另一个字符串时，会遇到如下图的情况我们通常的做法是从第一个串A的下一位B再逐位比... 查看详情

字符串匹配：kmp算法

一、原理：　　KMP算法是由Knuth，Morris，Pratt共同提出的模式匹配算法，其对于任何模式和目标序列，都可以在线性时间内完成匹配查找，而不会发生退化，是一个非常优秀的模式匹配算法。朴素算法（即暴力循环）的效率太差... 查看详情

字符串匹配--kmp算法原理整理

...原理:求出P0···Pi的最大相同前后缀长度k；字符串匹配是计算机的基本任务之一。举例,字符串"BBCABCDABABCDABCDABDE"，里面是否包含另一个字符串"ABCDABD"？许多算法可以完成这个任务，Knuth-Morris-Pratt算法（简称KMP）是最... 查看详情

kmp算法模式串匹配

转载：字符串匹配 kmp算法查看详情

kmp--字符串匹配

现在计算机处理涉及到大量的字符串操作，字符串的匹配是使用频率最高的字符串操作之一，大学数据结构与算法中字符串一章，也专门介绍了字符串匹配。字符串的单模式匹配中最基础的算法是朴素的模式串匹配算法，比这更... 查看详情

kmp算法(代码片段)

KMP算法写OJ时做到字符串匹配问题，用暴力算法结果超出时间限制了，其实早就知道这种问题可以用kmp算法解决，但是我一直懒得学，于是借助这个OJ来记录一下学习kmp算法的一些个人理解文章目录KMP算法字符串匹... 查看详情

kmp算法(代码片段)

kmp算法

KMP算法KMP算法的简介　　KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，简称KMP算法。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现... 查看详情

kmp算法

　　KMP算法简而言之就是告诉你一个字符串是否包含另一个字符串。　对于是否包含一个字符串，大部分人想做的就是挨个判断，但是这样并不是很优，所以就有了KMP。　　当你对A(被匹配)字符串和B(匹配)字符串进行匹配时... 查看详情

字符串的模式匹配：kmp算法

　　KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模... 查看详情

kmp算法(代码片段)

基本介绍KMP算法是一种用于字符串匹配的算法，网上关于kmp的介绍很多，也十分复杂，（其实我也没怎么搞懂）。首先我们还是考虑朴素的匹配，暴力枚举匹配起点，遇到不匹配的点，就直接退出，进行下一个起始点开始的一轮... 查看详情

kmp算法

参考：字符串匹配的KMP算法TheKnuth-Morris-PrattAlgorithminmyownwordsKMP算法详解从头到尾彻底理解KMP关键字：KMP算法面试字符匹配模式匹配推荐阮一峰的讲解，清晰明了。查看详情

kmp字符串匹配算法

一、概要：　　KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的(先了解BF算法)。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。二... 查看详情

字符串匹配的kmp算法(转)

KMP算法用于字符串匹配的，看到了一个非常通俗易懂的讲解，这里就转一下。http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html 查看详情

kmp算法小结

...个非常优秀的模式匹配算法。1.kmp算法的原理：1.首先，字符串"BBCABCDABABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。2.因为B与A不匹配，搜索词再往查看详情

kmp算法(代码片段)

1.KMP算法介绍在计算机科学中，Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可在一个字符串S内查找一个词W的出现位置。一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置，此算法利用... 查看详情