数据结构与算法——字符串匹配问题(KMP算法)

2020-04-30  本文已影响0人  A慢慢懂

了解KMP算法

KMP算法也是比较著名的模式匹配算法。是由D.E.Knuth,J.H.Morrs和VR.Pratt发表的一个模式匹配算法。可以大大避免重复遍历的情况。

KMP模式匹配算法原理

情况1:假设现在有一个主串S="abcdefgab";模式串T="abcdex";

如果使用暴风算法的话，前面五个字母完全相等，直到第六个字母"f"和"x"不相等。如下图：

image.png
接下来按照暴风算法，我们需要执行主串i=2，i=3，i=4，i= 5，i = 6的字母与子串T的首字母均相比较，均不相等即下图比较操作
i=2.png
i=3.png
i=4.png
i=5.png
i=6.png
按照暴风算法设计，我们执行过程就是这样，但是对于匹配的子串T来说，"abcdex"中的首字母"a"与后面的串"bcdex"的字母都不相等
那就是说既然"abcdex"中的首字母"a"与后面的串"bcdex"的字母都不相等，暴风算法中执行i=2，3，4，5的操作判断都是多余。
KMP算法就是利用这个已知信息，不把"搜索位置"移到已经比较过的位置，继续把它后移，这样就提高了效率。
理解KMP关键

情况2:假设现在有一个主串S="abcababca";模式串T="abcabx";

KMP匹配算法中_next数组的推导

情况1:模式串中无任何字符重复

T = “abcdex”
j 123456
模式串 abcdex
next[j] 011111

解读

情况2:模式串中类似"abcabx"

T = "abcabx"
j 123456
模式串T abcabx
next[j] 011123

解读

经验：如果前后缀一个字符相等，K的值是2，两个字符相等，K的值是3，n个相等K就是n+1；

情况3:模式串中类似"ababaaaba"

T = "ababaaaba"
j———————123456789
模式串T——— ababaaaba
next[j]————011234223

解读

情况4:模式串中类似"aaaaaaaab"

T = "aaaaaaaab"
j———————123456789
模式串T——— aaaaaaaab
next[j]————012345678

解读

KMP模式匹配算法实现

next数组其实就是求解字符串要回溯的位置
假设，主串S= “abcababca”;模式串T=“abcdex”，由以上分析得出next数组为011111，next数组意味着当主串与模式串不匹配时，都需要从第一个的位置重新比较。

image.png

KMP算法之next数组求解

#include <stdio.h>
#include "stdio.h"
#include "stdlib.h"

#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存储空间初始分配量 */

typedef int Status;        /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;    /* ElemType类型根据实际情况而定，这里假设为int */
typedef char String[MAXSIZE+1]; /*  0号单元存放串的长度 */
//----字符串相关操作---
/* 生成一个其值等于chars的串T */
Status StrAssign(String T,char *chars)
{
    int I;
    if(strlen(chars)>MAXSIZE)
        return ERROR;
    else
    {
        T[0]=strlen(chars);
        for(i=1;i<=T[0];I++)
            T[i]=*(chars+i-1);
        return OK;
    }
}

Status ClearString(String S)
{
    S[0]=0;/*  令串长为零 */
    return OK;
}

/*  输出字符串T。 */
void StrPrint(String T)
{
    int I;
    for(i=1;i<=T[0];I++)
        printf("%c",T[I]);
    printf("\n");
}

/* 返回串的元素个数 */
int StrLength(String S)
{
    return S[0];
}

void get_next(String T,int *next){
    int i ,j;
    i = 0;
    j = 1;
    next[1] = 0;
    //T[0]代表模式串的长度
    while (j<T[0]) {
        if (T[i] == T[j] || i == 0) {
            I++;
            j++;
            next[j] = I;
        }else{
            //回溯到原来的位置
            i = next[I];
        }
    }
}
//输出next的值
void next_print(int *next,int length){
    for (int i = 1; i <= length; i++) {
        printf(" %d",next[I]);
    }
    printf("\n");
}

KMP算法查找

int count = 0;
//返回子串T在主串S中的第pos个字符之后的位置，不存在则返回0
int Index_KMP(String S ,String T,int pos){
    int i = pos;
    int j = 1;
    //定义一个空的next数组
    int next[MAXSIZE];
    //T串的分析，得到Next数组
    get_next(T, next);
    count = 0;
    //S[0]和T[0]分别代表S和T串的长度
    while (i <= S[0] && j<=T[0]) {
        if (S[i]==T[j] || j==0) {
            I++;
            j++;
        }else{
            //如果不匹配时，j退回到合适的位置，i不变
            j = next[j];
        }
    }
    if (j>T[0]) {
        return  i- T[0];
    }else{
        return -1;
    }
}

KMP算法优化

KMP算法也是有缺陷的，比如主串S=“aaaabcde”,模式串T= “aaaaax”。next的数组就是012345；


image.png

当开始匹配时，当i= 5，j = 5时，我们发现字符"b"与字符“a”不相等，如上图，j = next[5] = 4;


image.png
image.png
image.png

由于T串的第二、三、四、五位置的字符都与首位“a”相等，那么可以用首位next[1]的值去取代与它相等的后续字符的next[j],那么next数组为{0,0,0,0,0,5};

KMP匹配模式next的数组优化

image.png
image.png
image.png
image.png

KMP_NextVal数组逻辑

在求解nextVal数组的5种情况

  1. 默认nextval[1]=0;
  2. T[i] == T[j]且++i，++j后依旧等于T[j],则nextval[i] = nextval[j]
    3.i = 0,表示从头开始i++，j++且T[i]!=T[j],则nextval[i] = j;
    4.T[i]==T[j],++i，++j后T[i]!=T[j]，则nextval[i] = j;
    5.当T[i]!=T[j]，表示不相等，则需要将i退回到合理位置，则i= next[i];

代码实现KMP_nextVal

void KMP_NextVal(String T ,int *next){
    int i,j ;
    i = 1;
    j = 0;
    next[1]=0;
    while (i<T[0]) {
        if (j==0 ||T[i] == T[j]) {
            ++i;
            ++j;
            if (T[i]!=T[j]) {
                next[i] = j;
            }else{
                next[i] = next[j];
            }
        }else{
            j = next[j];
        }
    }
    
}
上一篇 下一篇

猜你喜欢

热点阅读