KMP算法(算法篇)

算法之KMP算法

KMP算法

概念：

• KMP算法是用于解决字符串匹配的问题的算法，也就是有一个文本串和一个模式串，求解这个模式串是否在文本串中出现或者匹配。
• 相对于暴力求解，KMP算法使用了前缀表来进行匹配，充分利用了之前匹配的字符，减少了重新匹配全部模式串的时间。
• 时间复杂度为O(m+n)，其中n为文本串长度，m为模式串长度。

前缀表：

例子：文本串：‘aabaabaaf’ ，模式串：‘aabaaf’

• 前缀表也就是记录模式串的各子串最长相等前后缀长度(即字符串的前缀和后缀相等并且长度最长)的数组，而在KMP算法中是对模式串求解前缀表

• 前缀：字符串除了尾字符的子字符串都是前缀，模式串的前缀有：a、aa、aab、aaba、aabaa

• 后缀： 字符串除了首字符的子字符串都是后缀，模式串的后缀有：f、af、aaf、baaf、abaaf

• 

• 根据上述的例子可以列出表格：

  

• 这样就对应着：aabaaf 010120，这个就为前缀表，而前缀表在KMP算法中被称为next数组或者prefix数组。next的意思就是指通过这个数组可以知晓下一步指针会跳到哪一步。

求解next数组：

注：在遍历模式串的各个子串时，i为当前子串的后缀末尾索引，j为当前字串的前缀末尾索引并且为数组索引小于等于i之前的子串的最长相等前后缀长度。子串是连续的字符形成的

1. 初始化：j初始化为0，因为模式串的第一个前缀子串为第一个字符，所以j索引指向0的位置，并且next[0]=0，i初始化为1，用一个循环从索引i开始遍历模式串。(因为只有一个字符的子串没有相等前后缀)
2. 前后缀不相同情况：为了充分利用之前已经匹配的字符，我们将对发生冲突的地方也就是前后缀末尾字符不匹配的时候，我们将对前缀末尾索引进行回溯到索引为next[j-1]的位置。
3. 前后缀相同情况：当前后缀末尾字符相等的时候，就可以将j++，不仅将当前子串更新到下一个子串，还更新了当前子串的最长相等前后缀长度也就是next[i]=j

实现代码:

void getnext(int *next,const string& s,int size){
    //初始化
    int j=0;
    next[0]=0;
    for(int i=1;i<size;i++){
        //前后缀不相等情况
        while (j>0&&s[i]!=s[j]){
            j=next[j-1];    //回溯找到相等位置或者回到0
        }
        //前后缀相同情况
        if(s[i]==s[j]) j++;
        next[i]=j;
    }
}

KMP具体操作：

1. 求解next数组
2. 然后利用求解next数组同等思路，求解文本串出现模式串位置的索引，求解next数组是模式串前后缀末尾字符的比较，而文本串模式串匹配过程，是文本串与模式串的字符比较过程。
3. 当j也就是文本串在索引大于等于i之前的子串与模式串最长匹配字符长度等于模式串的长度，就说明文本串出现了模式串，然后返回文本串中出现模式串的第一个字符的索引值(i-j+1)。

KMP算法总体实现代码：

void getnext(int *next,const string& s,int size){
    //初始化
    int j=0;
    next[0]=0;
    for(int i=1;i<size;i++){
        //前后缀不相等情况
        while (j>0&&s[i]!=s[j]){
            j=next[j-1];    //回溯找到相等位置或者回到0
        }
        //前后缀相同情况
        if(s[i]==s[j]) j++;
        next[i]=j;
    }
}


int KMP(const string &text,const string &mode){
    int len=text.size();
    if(len==0) return 0;
    int size=mode.size();
    int j=0,next[size];
    getnext(next,mode,size);
    for(int i=0;i<len;i++){
        while (j>0&&text[i]!=mode[j]){
            j=next[j-1];
        }
        if(text[i]==mode[j]) j++;
        if(j==size) return (i-j+1);
    }
    return -1;    //未找到模式串
}