算法读书笔记第5章

/**
    Name:  KMP
    Author: Bryant_xw
    Date: 2018-11-28-15.25.30
*/

/**
    查找子串在主串中出现的位置
    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);
       //人为规定子串的第1个、第2个next数组的值是-1和0
     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 s1[] = "abcabcababaccc";
    char s2[] = "ababa";
    cout << "Match pos is: "<< KmpGetIndex(s1,s2) << endl;
    return 0;
}