KMP 算法

PathToYou

参考：结构之法，算法之道，阮一峰 字符串匹配的 KMP 算法

KMP

# KmpSearch.cpp

#include<iostream>
#include<cstring> 
using namespace std;
int next[101];
void GetNext(char* p,int next[])
{
    int pLen = strlen(p);
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < pLen - 1)
    {
        //p[k]表示前缀，p[j]表示后缀
        if (k == -1 || p[j] == p[k]) 
        {
            ++k;
            ++j;
            next[j] = k;
        }
        else 
        {
            // k 回溯，寻找长度更短的相同前缀后缀
            k = next[k];
        }
    }
}
int KmpSearch(char* s, char* p)
{
    int i = 0;
    int j = 0;
    int sLen = strlen(s);
    int pLen = strlen(p);
    while (i < sLen && j < pLen)
    {
        //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++    
        if (j == -1 || s[i] == p[j])
        {
            i++;
            j++;
        }
        else
        {
            //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]    
            //next[j]即为j所对应的next值      
            j = next[j];
        }
    }
    //若在 S 主串中找到 P 模式串，则返回在 S 中对应 P 第一个位置的下标；若未找到这样的子串，则返回 -1
    if (j == pLen)
        return i - j;
    else
        return -1;
}
int main(){
    char s[100],p[100];
    strcpy(s,"BBC ABCDAB ABCDABCDABDE");
    strcpy(p,"ABCDABD");
    GetNext(p,next);
    cout<<KmpSearch(s,p)<<endl;
    return 0;
}