KMP算法初探

[edit by xingoo]

kmp算法其实就是一种改进的字符串匹配算法。复杂度可以达到O(n+m),n是参考字符串长度,m是匹配字符串长度。

传统的算法,就是匹配字符串与参考字符串挨个比较,如果相同就比较下一个,如果不相同,就返回上一次的结果,再重新比较。

如图1 如果失败则字符串会重新用S(参考字符串)的第二个,与T(匹配字符串)的第一个比较,知道全部符合查找,或找不到为止。

此时发现S[5] != T[5],因此用S[1]与T[0]进行比较。

此时发现S[1]!=T[0],因此用S[2]与T[0]比较。

此时,仍然不相等,继续后移。

此时,S[3] == T[0],继续比较,发现所有T元素都在S中找到,满足查找,返回开始匹配的下标3.

传统代码

 1 int old_index(char * S,char * T){
 2     int i=0;
 3     int j=0;
 4     while(i<strlen(S) && j<strlen(T)){
 5         if( S[i] == T[j] ){
 6             ++i;
 7             ++j;
 8         }
 9         else{
10             i = i-j+1; //上一次的下一个
11             j=0;
12         }
13     }
14     if(j == strlen(T))
15         return i-strlen(T);
16     else
17         return -1;
18 }

这种比较忽略了一个问题,就是在T中,abcabx,第一个字符串因为不跟第二个,第三个一样,因此,在一开始的匹配中,可以直接跳过比较,直接从S的第三个元素开始比较。这里就涉及到一个概念:最短子串对称匹配。

首先,初始化,当j=0时,next(j)=-1;

当j=1时,字符串0到j-1,只有"a",因此 next(j) = 0;

当j=2时,字符串0到j-1,字符串为"ab",因此next(j) = 0;

当j=3时,字符串0到j-1,字符串为"abc",因此next(j) = 0;

当j=4时,字符串0到j-1,字符串为"abca",此时,前缀a在末尾出现,因此next(j) = 1;

当j=5时,字符串0到j-1,字符串为"abcab",此时,前缀ab在末尾出现,因此next(j) = 2;

最后得到next的数组为"-1 0 0 0 1 2"。

按照这个方法:

ababab的next数组为"-1 0 0 1 2 3 4"

这里面,当j=5时,字符串"ababa",前缀是"aba",后缀也是"aba",因此next值为3.

计算next数组详细代码

void getNext(char * T,int *next){
    int i,j;
    i=0;
    j=-1;
    next[0]=-1;
    while(i<strlen(T)){
        if(j == -1 || T[i] == T[j]){
            ++i;
            ++j;
            next[i] = j;
        }
        else{
            j = next[j];
        }
    }
}

kmp匹配代码

int kmp(char* S,char * T){
    int i=0;
    int j=0;
    int next[MAX];
    getNext(T,next);
    while(i<strlen(S) && j<strlen(T)){
        printf("i %d-%c j %d-%c\n",i,S[i],j,T[j]);
        if(j==0 || S[i]==T[j]){
            ++i;
            ++j;
        }else{
            j = next[j];
            printf("j back to %d\n",j);
        }
    }
    if(j == strlen(T))
        return i-strlen(T);
    else
        return 0;
}

全部代码

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #define MAX 20
 5 
 6 void getNext(char * T,int *next);
 7 int kmp(char * S,char * T);
 8 int old_index(char * S,char * T);
 9 
10 int main()
11 {
12     char * s = "acabbabababc";
13     char * t = "ababab";
14 
15     //printf("the pos is:%d\n\n",old_index(s,t));
16     //printf("the pos is:%d\n\n",old_index(m,t));
17     //printf("the pos is:%d\n\n",old_index(n,t));
18     printf("the pos is:%d\n",kmp(s,t));
19     return 0;
20 }
21 
22 void getNext(char * T,int *next){
23     int i,j;
24     i=0;
25     j=-1;
26     next[0]=-1;
27     while(i<strlen(T)){
28         if(j == -1 || T[i] == T[j]){
29             ++i;
30             ++j;
31             next[i] = j;
32         }
33         else{
34             j = next[j];
35         }
36     }
37 }
38 
39 int kmp(char* S,char * T){
40     int i=0;
41     int j=0;
42     int next[MAX];
43     getNext(T,next);
44     while(i<strlen(S) && j<strlen(T)){
45         printf("i %d-%c j %d-%c\n",i,S[i],j,T[j]);
46         if(j==0 || S[i]==T[j]){
47             ++i;
48             ++j;
49         }else{
50             j = next[j];
51             printf("j back to %d\n",j);
52         }
53     }
54     if(j == strlen(T))
55         return i-strlen(T);
56     else
57         return 0;
58 }
59 int old_index(char * S,char * T){
60     int i=0;
61     int j=0;
62     while(i<strlen(S) && j<strlen(T)){
63         if( S[i] == T[j] ){
64             ++i;
65             ++j;
66         }
67         else{
68             i = i-j+1; //上一次的下一个
69             j=0;
70         }
71     }
72     if(j == strlen(T))
73         return i-strlen(T);
74     else
75         return -1;
76 }

运行结果

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏闻道于事

Java之异常处理

Java异常处理 异常:异常就是Java程序在运行过程中出现的错误。 异常由来:问题也是现实生活中一个具体事务,也可以通过java 的类的形式进行描述,并封装成...

34560
来自专栏技术之路

typedef 和define的区别

总结一下typedef和#define的区别 1.概念   #define 它在编译预处理时进行简单的替换,不作正确性检查。它是预处理指令。   typedef...

20970
来自专栏企鹅号快讯

Python这些问题你都会吗?

距离Python圣诞学习狂欢夜 还有4天 点击进入详细了解 final作用域的代码一定会被执行吗? 正常的情况下,finally作用域的代码一定会被执行的,不管...

24450
来自专栏Python小屋

Python计算整数阶乘的几种方法比较

问题本身很简单,主要是通过这个小问题来演示Python的一些用法,例如测试代码运行时间、函数嵌套定义等等。 from time import time from...

95670
来自专栏黑泽君的专栏

throws 与 throw

/* * 有些时候,我们是可以对异常进行处理的,但是又有些时候,我们根本就没有权限去处理某个异常。 * 或者说,我处理不了,我就不处理了。 * 为了解决出...

24220
来自专栏开发与安全

从零开始学C++之异常(三):异常与继承、异常与指针、异常规格说明

 一、异常与继承 如果异常类型为C++的类,并且该类有其基类,则应该将派生类的错误处理程序放在前面,基类的错误处理程序放在后面 #include <iost...

19500
来自专栏java 成神之路

JAVA对象在JVM中内存分配

403120
来自专栏Bug生活2048

Python自学之路-list、tuple、dict和set

上一篇「Python自学之路-数据类型和变量」主要简单说明了下数据类型和变量,这一篇主要和大家介绍下list、tuple、dict和set。相信后期在实战中会经...

13520
来自专栏web前端教室

十一国庆节 之 “变量与函数同名时,会输出谁?”

看这样一个题目: b = function c() { a = 1, b = 2, c = 3; console.log(a); //1 ...

192100
来自专栏水击三千

浅谈JavaScript的函数表达式(递归)

  递归函数,在前面的博客中已经简单的介绍了。递归函数是一个通过函数名称在函数内部调用自身的函数。如下: 1 function fac(num){ 2 ...

256100

扫码关注云+社区

领取腾讯云代金券