BF和KMP模式匹配算法

在进行字符串匹配的相关程序中，看一个子串是否在一个主串里面，有著名的Brute-Force和基于此改进的KMP算法，具体学习记录如下：

Brute-Force

①BF算法算是一种暴力算法，首先是查看t的第一字母a和上面s的第一个字母比较相同，所以接着比较比到各自的第三个字符也就是，aba、abc发现不同，

②再递推比较，t回到第一个字母a，这时s回到第二个字符（因为第一个字符已经比过了）相当于babcabcacbab和abcac两个字符串进行比较，很明显第一个字符就不一样，

③再递推比较……

按常理来思考，这样总能得出结果，但是在此基础上，可以有进一步的优化操作，怎么说？

在上面的第②步里面，我们总是一步一步递推，那我们能不能一次性推好几步呢？就根据已经匹配了的那串字母。

具体表现为：①已经发现是第三个字符不同，那我们就根据前面两个相同的字符（ab）推出第②步推两步，为什么根据相同的ab，第②个步骤就可以一次性走两步？

KMP算法

算法详述

先学会用，理论日后再补…… 🕊

计算next函数值

方法：

①next数组第一位永远是0，1；

②next(j) = 前序列相同元素个数 + 1；

eg：当t = 6：

前面的序列为ababa，可以看出相同的子序列为aba，相同元素个数为3，所以next(6) = 3 + 1 = 4

注意：不能“全覆盖”，比如当j = 2时候，前面的a不能看成a = a序列，这样就变成next(2) = 2了；

计算next函数修正值

方法：

①先列举出next(j)，求nextval(j)是基于next(j)的；

②求nextval(j)，先看求next(j)的值，记这个值为x；

③在表格中找出j = x的那一列，如果这一列的t值和②步骤中的t值相同，则结果为j = x这一列的nextval(j)值，如果不相同，则结果为所要求的那一列的next(j)值；

eg：当j = 5时：

此时next(j) = 3，就去j = 3那一列看到t = a，和j = 5一列的t值a相同，所以结果为j = 3一列的nextval值0

eg：当j = 6时：

此时next(j) = 4，就去j = 4那一列看到t = b，和j = 6一列的t值不相同，所以结果为j = 6一列的next值4

具体匹配情况

答案：

代码

#include<bits/stdc++.h>
using namespace std;
typedef int Status;
typedef int ElemType;
#define OVERFLOW -1
#define ERROR 0
#define OK 1

//------串的顺序存储结构-----
#define MAXLEN 225
typedef struct 
{
    char ch[MAXLEN + 1];    //存储串的一维数组，从下标为1的数组分量开始存储的，下标为0的分量闲置不用 
    int length;             //串的当前长度
}SString;

//------串的堆式顺序存储结构-----
typedef struct 
{
    char *ch;       //若是非空串，则按串长分配存储区，否则ch为NULL
    int length;     //串的当前长度
}HString;

HString S, T;

//-----串的链式存储结构-----
#define CHUNKSIZE 80
typedef struct Chunk
{
    char ch[CHUNKSIZE];
    struct Chunk *next;
}Chunk;
typedef struct
{
    Chunk *head, *tail;     //串的头指针和尾指针
    int length;             //串的当前长度
}LString;

// //1、生成串
// StrAssign(&T, chars)

// //2、复制
// StrCopy(&T, S)

// //3、判空
// StrEmpty(S)

// //4、比较
// StrCompare(S, T)

// //5、长度
// StrLength(S)

// //6、清空
// ClearString(&S)

// //7、联接
// Concat(&T, S1, S2)

// //8、子串
// SubString(&Sub, S, pos, len)

//9、串的模式匹配_BF算法 O(n * m)
int Index_BF(HString S, HString T, int pos)
{//返回模式T在主串s中第pos个字符开始第一次出现的位置。若不存在，则返回值为0
 //其中，T非空，1<=pos<=S.length
    int i = pos, j = 1;                     //初始化
    while(i <= S.length && j <= T.length)   //两串均未比较到串尾
    {
        if(S.ch[i] == T.ch[j])              //继续比较后继字符
        {
            i++;
            j++;
        }
        else                                //指针后退重新开始匹配
        {
            i = i - j + 2;                  //i=i-j+1回到i的起点，+2到下一个字符
            j = 1;
        }
    }
    if(j > T.length)
            return i - T.length;            //匹配成功，返回T在S中第一次出现的位置
        else
            return 0;
}

//9、串的模式匹配_KMP算法求next数组
void get_next(HString, int next[])
{//求模式串T的next函数值并存入数组next
    int j = 1, t = 0;
    next[1] = 0;
    while(j < T.length)
    {
        if(t == 0 || T.ch[j] == T.ch[t])
        {
            t++;
            j++;
            next[j] = t;
        }
        else
            t = next[t];
    }
}

//9、串的模式匹配_KMP算法求nextval数组
void get_nextval(HString T, int nextval[])
{//求模式串T的next函数修正值并存入数组nextval
    int j = 1, t = 0;
    nextval[1] = 0;
    while(j < T.length)
    {
        if(t == 0 || T.ch[j] == T.ch[t])
        {
            t++;
            j++;
            if(T.ch[j] != T.ch[t])
                nextval[j] = t;
            else
                nextval[j] = nextval[t];
        }
        else
            t = nextval[t];
    }
}

//9、串的模式匹配_KMP算法 O(n + m)
int Index_KMP(HString S, HString T, int pos, int next[])
{//利用模式串T的next函数求T在主串S中第pos个字符之后的位置
 //其中，T非空，1<=pos<=S.length 
    int i = pos, j = 1;
    while(i <= S.length && j <= S.length)   //两个串均未比较到串尾
    {
        if(j == 0 || S.ch[i] == T.ch[i])    //继续比较后继字符
        {
            i++;
            j++;
        }
        else
            j = next[j];                    //模式串向右移动
        if(j > T.length)                    //匹配成功
            return i - T.length;
        else
            return 0;
    }
}

// //10、插入
// Strlnsert(&S, pos, T) 

// //11、删除
// StrDelete(&S, pos, len)

// //12、销毁
// DestroyString(&S)