模式串从 0 开始的KMP算法

Blithe-Chiang 2020-10-04 原文


/**
 *  看了 b站视频 BV1jb411V78H 对KMP有了一点理解，然后我写了这个代码
 *  这个代码和视频里面的有一点不同，字符串是从 0 开始的，而不是从1 开始的
 *  希望能够帮到学习KMP的人
 */


#include <stdbool.h>
#include <malloc.h>
#include "KMP.h"

// KMP.h 内容
/*
#define MAXSIZE (255)

typedef struct {
    char ch[MAXSIZE + 1];
    int length;
}SString;

void Next(SString const *t);
extern int *next;
int IndexOf_KMP(SString const *s, SString const *t);
*/

int *next;      // 计算 next数组

/**
 * 计算 0-based 模式串t的next数组
 * @param t 模式串
 */
void Next(SString const *t) {
    //  模式串 0 开始
    int length = t->length;

    // 分配 next数组 所需要的空间
    next = (int *)malloc(sizeof(int) * length);
    for (int *p = next; p < next + length; p++)
    {
        *p = 0;
    }

    for (int i = 0; i < length; i++)
    {
        if (i <= 1)     // 前两个next[i]置为-1
        {
            next[i] = -1;
            continue;
        }

        // 执行下面的语句的时候， 一定有 i >= 2



        int maxlen = 0;         // 存储最长公共前后缀的长度

        /**
         *  // len 表示前缀或后缀的最大长度, 可取的值是 [1..i-1]      // i 为(模式串或next数组)的访问下标
         *  这里主要是 对 模式串在i位置 求 它的最大公共前后缀的长度
         *  从 1 开始 到 i-1 一个一个去试 
         *  
         */
        for (int len = 1; len < i; len++)
        {
            int val = 0;
            bool flag = false;

            for (int j = 0, k = i - len; j < len; j++, k++)
            {
                if (t->ch[j] == t->ch[k])
                {
                }
                else
                {
                    flag = true;        // len 长度的公共前后缀匹配失败
                    break;
                }
            }

            if (flag == false)          //  公共前后缀长度为len
                val = len;
            if (val > maxlen)           // 这个比较不是必须的，因为找公共前后缀的长度的时候， len 从 1 到 i-1
                maxlen = val;           // maxlen 就是 next[i]的值了
        }
        next[i] = maxlen;
    }
}

// 调用这个函数之前，一定要调用 Next函数，为模式串构建 next数组
int IndexOf_KMP(SString const *s, SString const *t)
{
    // 开始匹配

    int i = 0, j = 0;       // i 表示主串的下标， j 表示模式串的下标
    while (i < s->length)
    {
        if (j == -1 || s->ch[i] == t->ch[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }

        // 匹配成功
        if (j == t->length)
        {
            return i - t->length;
        }
    }

    // 匹配失败
    return -1;
}