KMP算法

kmp.hpp

//
//  kmp.hpp
//  test
//
//  Created by 王璟 on 2019/4/17.
//  Copyright © 2019年 王璟. All rights reserved.
//

#ifndef kmp_hpp
#define kmp_hpp

#include <iostream>
#include <string>
using namespace std;

int* get_next(const string& T);
int* get_nextval(const string& T);
int index_kmp(const string& S, const string& T, int *next);
int get_index(const string& S, const string& T);
#endif /* kmp_hpp */

kmp.cpp

//
//  kmp.cpp
//  test
//
//  Created by 王璟 on 2019/4/17.
//  Copyright © 2019年 王璟. All rights reserved.
//

#include "kmp.h"

/*
 算法讲解：
    KMP算法主要是通过模式串自身生成一个next数组，在模式串和主串匹配不上的时候利用next数组尽可能的向右推进一部分距离，
 因为模式串里面可能存在部分相同区域（例如ABA），主串要是已经完成了第二个A区域的匹配，那么模式串只需要回到第一个A的位置继续与主串匹配，而不是直接回到一开始进行匹配，
 算法的时间复杂度在O(m+n)
 */


/*
 KMP算法中获取模式串T的next数组
|   j  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|   p  | a | b | a | a | b | c | a | c |
| next | 0 | 0 | 0 | 1 | 1 | 2 | 0 | 1 |

 next[0] = 0, next[1] = 0;
 后面的next的值要看从该坐标前面的和0开始的串能匹配多少个；
 eg：坐标为 3的‘a’,前面是坐标为2的‘a’,与0开始的串匹配到了长度为1的串‘a’，因此其next[4] = 1
     坐标为5的‘c’，前面是“ab”匹配z坐标0到1的“ab”，因此其next值为2
*/
int* get_next(const string& T)
{
    int T_len = T.size();
    int *next = new int[T_len];
    next[0] = 0;
    next[1] = 0;
    int i = 0, j = 0; // i为快下标 j为慢下标(为了完成模式串中例如ABA中A与A的匹配)
    for(i = 2; i < T_len;){
        if(T[i-1] == T[j]){
            // 如果当前快下标i的前一个元素T[i-1]和慢下标T[j]匹配上了，
            // 那么证明该快下标i对应next[i]数组的数值为j+1，到时候可以直接回到j+1的位置，因为前面已经成功匹配过一次了
            next[i] = ++j;  
            ++i;
        }else if(0 == j){
            // 如果此时存在 T[j] != T[i-1]，当快下标的前一个元素和慢下标元素没有匹配上，而且此时的慢下标j==0，
            // 那么当前的next数值肯定为0,说明当前快下标前面的元素都没有完成一个与慢下标的匹配关系，那么就只能直接回到下标为0的位置重新匹配
            next[i] = 0;
            ++i;
        }else{
            // 如果此时存在 T[j] != T[i-1] 同时 j!=0那么将j进行回溯
            j = next[j];
        }
    }
    return next;
}


// 改进的KMP算法中获取模式串T的next数组
/*
 改进的KMP算法主要针对于"aaaab"这种类型进行了优化，在原来next数组里面为0 0 1 2 3，
 但是在模式串与主串aaaacaaaab的匹配中，第一次匹配到T[j=4] = b, T[i=4] = c的时候m，两者匹配不成功，
 此时如果利用next数组的话，就是先回到3->2->1->0;但是我们可以发现T[3] = T[2] = T[1] = T[0]都是等于a的，可以直接从3就回到了0；
 所以在构造改进的nextval的时候，在匹配上的时候，需要注意如果我们发现T[i] = T[j+1]的时候，直接让nextval[i] = nextval[++j];
 分析：在匹配上的时候，如果我们当前的T[i]在原有的算法里面是直接next[i] = ++j; 如果T[i] == T[j+1]的话，主串在匹配不上T[i]的时候同样等于直接匹配不上T[j+1]，所以存在如上的结果；
 （要注意j的数值还是要继续前进的），只要存在匹配成功的情况，都要将匹配的信息保留在j中
 */
int* get_nextval(const string& T)
{
    int T_len = T.size();
    int *nextval = new int[T_len];
    nextval[0] = 0;
    nextval[1] = 0;
    int i = 0, j = 0; // i为快下标 j为慢下标(为了完成模式串中例如ABA中A与A的匹配)
    for(i = 2; i < T_len;){
        if(T[i-1] == T[j]){
            // 如果当前快下标i的前一个元素T[i-1]和慢下标T[j]匹配上了，
            // 那么证明该快下标i对应next[i]数组的数值为j+1，到时候可以直接回到j+1的位置，因为前面已经成功匹配过一次了
            if(T[i] == T[j+1]) nextval[i] = nextval[++j];
            else nextval[i] = ++j;
            ++i;
        }else if(0 == j){
            // 如果此时存在 T[j] != T[i-1]，当快下标的前一个元素和慢下标元素没有匹配上，而且此时的慢下标j==0，
            // 那么当前的next数值肯定为0,说明当前快下标前面的元素都没有完成一个与慢下标的匹配关系，那么就只能直接回到下标为0的位置重新匹配
            nextval[i] = 0;
            ++i;
        }else{
            // 如果此时存在 T[j] != T[i-1] 同时 j!=0那么将j进行回溯
            j = nextval[j];
        }
    }
    return nextval;
}

// 通过KMP算法进行模式串和主串的匹配，返回第一次匹配成功的下标（没有匹配成功返回-1）
int index_kmp(const string& S, const string& T, int *next)
{
    int i = 0, j = 0;
    while(i < S.size() && j < T.size()){
        if(S[i] == T[j]){ // 匹配上的时候
            ++i;
            ++j;
        }else{
            if(0 == j) ++i; // 全部都匹配不上的时候主串需要向前移动了
            else j = next[j];
        }
    }
    if(j >= T.size()){ // 表示完成匹配
        return  i - j;
    }else return -1;
}


// 普通匹配算法
int get_index(const string& S, const string& T)
{
    int i = 0, j = 0;
    while(i < S.size() && j < T.size())
    {
        if(S[i] == T[j]){
            ++i;
            ++j;
        }else{
            i = i - j + 1;
            j = 0;
        }
    }
    if(j >= T.size()) return i - j;
    else return -1;
}