字符串匹配算法——kmp

实现原理：
kmp算法核心是next数组（是针对子串所设定的）的求解，也就是最大前缀和最大后缀的匹配。（规定最大前缀不包含最后一个字符，最大后缀不包含第一个字符）

代码中会有一些注解，想看更加详细的解释可以看一下这篇博客
代码

/**
    查找子串在主串中出现的位置
    str1:abcabcababaccc
    str2:ababa
    返回POS = 6
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
using namespace std;

//获取next数组
vector<int> getNextArr(char str2[]){
    int len = strlen(str2);
    vector<int> next(len);
    next[0] = -1;
    next[1] = 0;
    int i = 2;
    int cn = 0;
    while(i < next.size()){
        if(str2[i-1] == str2[cn]){
            next[i++] = ++cn;
        }else if(cn > 0){
            cn = next[cn];	//回溯
        }else{
            next[i++] = 0;
        }
    }
    return next;
}

//获取Index
int KmpGetIndex(char str1[], char str2[]){
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    cout<<"len1:"<<len1<< " "<<str1<<endl;
    cout<<"len2:"<<len2<< " "<<str2<<endl;
    if(len2 > len1 || len2 < 1)
        return -1;
    int i = 0;
    int j = 0;
    vector<int> next = getNextArr(str2);
    while(i < len1 && j < len2)
    {
        if(str1[i] == str2[j]){
            i++, j++;
        }else if(next[j] == -1){	//子串已经是第一个字符，则只需向右更新母串的下标
            i++;
        }else {
            j = next[j];	//子串向左更新下标
        }
    }
    return j == len2 ? i - j : -1;
}



int main()
{
	char test[] = "aabaabacbaaaaba";
	int length = strlen(test);
	vector<int>next()
    char s1[] = "abcabcababaccc";
    char s2[] = "ababa";
    cout << "Match pos is: "<< KmpGetIndex(s1,s2) << endl;
    return 0;
}

字符串匹配算法——kmp

相关推荐