数据结构:字符匹配算法


[success]研究这个算法,着实研究了我好久,特别是kmp算法,现在都还有点蒙,不过还是可以大概理解的,这里代码部分kmp不好解释,所以我就直接上图了。[/success]

字符串匹配算法就是相当于在字符串中查找某个字符串,有两种实现算法,一个是BF算法,还有一个是KMP算法,先讲一下BF算法。

BF算法其实就是一个不断匹配的算法,S作为主串每次匹配失败后只移动一位,而T则不断从头开始继续和S进行匹配。BF算法,容易理解,下面重带讲那个难以理解的KMP算法(这里我参考了别人的博客(传送门)):

首先我们讲一下一个概念:前缀和后缀

前缀:指的是字符串的子串中从原串最前面开始的子串,如abcdef的前缀有:a,ab,abc,abcd,abcde
后缀:指的是字符串的子串中在原串结尾处结尾的子串,如abcdef的后缀有:f,ef,def,cdef,bcdef

KMP算法引入了一个next数组,next[j]表示的是前j-1的字符组成的这个子串最长的相同前缀后缀的长度!
怎么理解呢?
例如字符串aababaaba的相同前缀后缀有a和aaba,那么其中最长的就是aaba。

注意:我们后面的字符串都是从1开始的,数组的第0位我们不用,所以解释上和我参考的博客是不一样的,next的值也是不一样的,请大家自行理解原理,不要死记

这里我举一个例子:

B=    "a b a a b c a c"
next= 0 1 1 2 2 3 1 2

next为0就是说如果第一个都不匹配的话,那么继续匹配。如果为1,说明没有相同的最长前缀和后缀。

比如我们拿next[5],next[6],next[7]分别说明一下next[5]为2,说明前j-1=4个字符“abaa”中最长相同前缀和后缀是1也就是a,那么下次匹配时直接从第2位开始。next[6]为3,那么前j-1=5个字符"abaab"最大相同前缀后缀是"ab",(这里就是倒着数和顺着数(这里不是真的倒着数)前面出现的都有ab),next[7]为1,"abaabc"说明没有相同的字符,所以B要从头开始比较。

注意:这里前缀和后缀是理解next的关键

有了这个next后,我们就可以开始匹配了(这里我贴一张别人的图片)

其实原理很简单,就是S主串每次匹配都会+1,而子串每次也是加1,只是如果不匹配的话,那么字符就会回到第next[j]位上重新进行比较,而i是不变的

重要的是理解下面这个代码。

if (j == 0 || S.ch[i] == T.ch[j]) { ++i, ++j; }
else j = next[j];

这个是什么原理呢?

其实就是利用了前面那个相同前缀和后缀,比如我们匹配时发现有S和T不匹配,那么我们知道,S和T前面都是相同的(指的是S前面和T匹配的部分),我们可以把S看成B的后缀,那么我们可以根据next知道和B后缀相同的最长前缀是第几位,那么,B就不需要从头开始了,直接从这位开始,因为前面这几位和S是匹配的

那么直接上代码了:

//串的存储结构
#include"pch.h"
#include <iostream>
using namespace std;
//串有3种存储结构:顺序存储,堆式顺序存储,链式存储
//顺序存储
#define MAXLEN 255 //定义串的最大长度
typedef struct
{
    // 我们声明数组时需要多申明一个,目的是保留一位作为结束位
    char ch[MAXLEN + 1];
    int length;
}SString;
//-------串的堆式顺序存储结构
typedef struct {
    //相当于这个ch*是一个指向数组首地址的指针
    char *ch;
    int length;
}HString;
//---串的链式存储结构
#define CHUNKSIZE 80//这里是块的大小
typedef struct Chunk
{
    char ch[CHUNKSIZE];
    struct Chunk *next;
}Chunk;
typedef struct
{
    Chunk *head, *tail;//定义了头尾指针,分别指向头尾
    int length;
}LString;
/*
这里因为时间的关系,所以我这里也不说字符串怎么添加,我们这里直接说一下
字符串匹配的算法,字符串有两种匹配的算法,一个是BF算法,一个是KMP算法
*/
int Index_BF(SString S, SString T, int pos)
{
    //BF算法就是,两个串不断进行匹配,如果相等就继续向下匹配,如果不等,那么指针就要后退重新开始匹配
    //这个pos就是开始匹配的位置
    int i = pos, j = 1;
    while (i <= S.length && j <= T.length)//两个字符串均未到达末尾
    {
        //这里就是如果I超了,就说明匹配失败,如果j超了就说明匹配成功
        if (S.ch[i++] !=T.ch[j++])  { i = i - j + 2; j = 1; }
        //上面是不断比较,如果发现有不一样的那么i就要回退i-j+2,j要回到1
        //之所以是i-j+2 是相当于比较了j个字符,然后i要回退j个字符(i-j+1)在原来的基础上在加1
    }
    if (j > T.length) return i - T.length;//如果j>T.length说明匹配成功,那么就返回字符串的起始位置
    else return 0;
}
//KMP算法的实现
//这个算法的改进在于每当一趟匹配出现不相等时,不需要回溯i指针,而是利用已得到的“部分匹配结果”,
//只需要j回退就可以继续进行匹配
//在进行KMP算法之前,我们需要先计算next的值
void get_next(SString T, int next[8])
{
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T.length)
    {
        //next就是计算相同前缀的长度的值
        if (j == 0 || T.ch[i] == T.ch[j]) { ++i; ++j; next[i] = j; }
        else j = next[j];
    }
}
int Index_KMP(SString S, SString T, int pos, int next[8])
{
    int i = pos, j = 1;
    while (i<=S.length && j<=T.length)
    {
        //kmp算法,就是i不断的进行+,不回溯,j则根据next的值,自己回溯
        if (j == 0 || S.ch[i] == T.ch[j]) { ++i, ++j; }
        else j = next[j];
    }
    if (j > T.length) return i - T.length;
    else return 0;

}
int main()
{
    SString *S = new SString;
    S->length = 17;
    S->ch[1] = 'a';
    S->ch[2] = 'c';
    S->ch[3] = 'a';
    S->ch[4] = 'b';
    S->ch[5] = 'a'; 
    S->ch[6] = 'a';
    S->ch[7] = 'b';
    S->ch[8] = 'a';
    S->ch[9] = 'a';
    S->ch[10] = 'b'; 
    S->ch[11] = 'c';
    S->ch[12] = 'a';
    S->ch[13] = 'c';
    S->ch[14] = 'a';
    S->ch[15] = 'a';
    S->ch[16] = 'b';
    S->ch[17] = 'c';
    SString *T= new SString;
    T->length = 8;
    T->ch[1] = 'a';
    T->ch[2] = 'b';
    T->ch[3] = 'a';
    T->ch[4] = 'a';
    T->ch[5] = 'b';
    T->ch[6] = 'c';
    T->ch[7] = 'a';
    T->ch[8] = 'c';
    //先初始化我们的字符串,这里为了方便起见,我就不给0赋值
    int i = Index_BF(*S, *T, 1);
    cout <<"字符的位置在:"<<i << endl;
    int next[9] ;
    get_next(*T, next);
    cout << Index_KMP(*S, *T, 1, next);
    return 0;
}

至于这个next值是怎么计算的呢?

int i = 1, j = 0;
next[1] = 0;
while (i < T.length)
{
    //next就是计算相同前缀的长度的值
    if (j == 0 || T.ch[i] == T.ch[j]) { ++i; ++j; next[i] = j; }
    else j = next[j];
}

我们可以看到,这个i就相当于在计算后缀,而j则是充当前缀的角色。就相当于B前i位的后缀和B前j位的前缀进行比较,如果匹配就记下j(这个j其实就是最大的前缀数,因为B的前j位和i的后i位是匹配的)

好了,这个算法就解释到这里,最后还想吐槽下,这个算法还是不好理解,研究了两天才勉强看懂。


文章作者: 小游
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 小游 !
  目录