模式串 從 0 開始的KMP演算法

• 2020 年 10 月 4 日
• 筆記
• KMP, 演算法

/**
 *  看了 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;
}