KMP算法

KMP算法是字符串匹配算法，主要有两步组成：

• step1:简历PrefixTable，求出小于本身的最长公共前后缀；

• step2 ：根据PrefixTable进行KMP搜索；

C++代码：

#include<iostream>
using namespace std;
//创建前缀表
void PrefixTable(char pattern[], int prefix[], int n)
{
    prefix[0] = 0;
    int len = 0;
    int i = 1;
    while (i < n)
    {
        if (pattern[i] == pattern[len])
        {
            len++;
            prefix[i] = len;
            i++;
        }
        else
        {
            if (len > 0)
            {
                len = prefix[len - 1];
            }
            else
            {
                prefix[i] = len;
                i++;
            }
        }
    }
}
//移动prefixtable，使得开始为-1
void MovePrefix(int prefix[], int n)
{
    for (int i = n - 1; i > 0; i--)
    {
        prefix[i] = prefix[i - 1];
    }
    prefix[0] = -1;
}
//KMP搜索
void Kmp_Search(char text[], char pattern[])
{
    int n = strlen(pattern);
    //试过int prefix[n]是错误，因为初始化数组必须n要常数
    int *prefix = (int *)(malloc(sizeof(int)*n));
    PrefixTable(pattern,prefix,n);
    MovePrefix(prefix,n);
    int m = strlen(text);
    int i = 0;
    int j = 0;
    while (i < m)
    {
        if (j == n - 1 && text[i] == pattern[j])
        {
            cout << i - j << endl;
            j = prefix[j];
        }
        if (text[i] == pattern[j])
        {
            i++;
            j++;
        }
        else
        {
            j = prefix[j];
            if (j == -1)
            {
                i++;
                j++;
            }
        }

    }
}
int main()
{
    char pattern[] = "ababc";
    char Text[] = "abaacababcac";
    Kmp_Search(Text,pattern);
    return 0;
}

本文代码来自两个讲解KMP算法的视频，亲自实现无误！