[C++知识库]纯C++实现KMP算法（附解析与时间复杂度分析）

#include "iostream"

#define MAXSIZE 100
using namespace std;

int getIndexOf(string str1, string str2);

//求next数组
int *getNextArr(string str);

int main() {
    string str = "abdes";
    string t = "de";
    cout << getIndexOf(str, t);
}

int getIndexOf(string str1, string str2) {
    if (str1.empty() || str2.empty() || str2.length() < 1 || str1.length() < str2.length()) {
        return -1;
    }

    //str1中对比到的位置
    int x = 0;
    //str2中对比到的位置
    int y = 0;
    //next数组
    int *next = getNextArr(str2);

    /*
     * while时间复杂度分析：
     * 因为三个分支互斥，所以分析时间复杂度只需要把三个分支的时间复杂度相加
     * 两个量：x（时间复杂度最大值：N），x-y（时间复杂度最大值：N【x=N，y=0】）
     *      逻辑分支1：x++,y++
     *      逻辑分支2：x++
     *      逻辑分支3：x不变，y减小
     *  两个量加起来的最大值是2N，即三个逻辑分支相加，总次数不会超过2N的水平
     *  所以整体不会超过b个O（N）的复杂度
     */
    //跳出循环的条件：要么x越界，要么y越界（当y越界时说明已经在str1中找到了匹配的字符串，否则str1中没有匹配的字符串）
    while (x < str1.length() && y < str2.length()) {
        //当前位置str1与str2匹配
        if (str1[x] == str2[y]) {
            ++x;
            ++y;
        } else if (next[y] == -1) {//当前位置str1与str2不匹配，且y位置的next数组的值为-1（此时y的值为0，因为没有最大公共前后缀）
            //因为str1的当前位置与str2中都不匹配，所以需要从str1的下一个位置进行匹配
            ++x;
        } else {//当前位置str1与str2不匹配，且y位置的next数组的值不是-1
            //y -> 4 说明下标(0 1 2 3)是不用配的东西，待定的位置来到4，即（0，1，2，3）4
            y = next[y];//x不变，y往回跳
        }
    }

    //判断y是否越界，如果越界则返回str1中匹配的开头位置，否则返回-1表示没有匹配（即不含有str2）
    return y == str2.length() ? x - y : -1;
}

/*
 * 时间复杂度计算
 * 设str2长度为M
 *      第一个逻辑分支： i 增加，currentNumber也增加
 *      第二个逻辑分支：currentNumber减小
 *      第三个逻辑分支：i 增加
 *  三个逻辑分支互斥，所以有两个量：i（最大值为M），i-currentNumber（最大值为M）
 *      第一个逻辑分支：i(M)↑，i-currentNumber(M)不变
 *      第二个逻辑分支：i(M)不变，i-currentNumber(M)↑
 *      第三个逻辑分支：i(M)↑，i-currentNumber(M)↑
 *  所以while最大的时间复杂度不会超过2M，即时间复杂度为O（M）
 */
int *getNextArr(string str) {
    //字符串中只有一个字符，让next数组为-1（人为规定）
    if (str.length() == 1) {
        return new int[1]{-1};
    }

    //next数组生成
    int *next = new int[str.length()];
    //人为规定next数组0位置是-1，1位置是0
    next[0] = -1;
    next[1] = 0;
    //因为0，1上的信息都有了，所以从下标2开始求
    int i = 2;
    //表示当前所在位置的字符是和 i-1 位置的字符比较（也代表 i-1 位置的next数组值）
    int currentNumber = 0;

    //依次每个位置去求next数组的值
    while (i < str.length()) {
        //如果当前 i-1 位置的字符等于跳到位置的字符
        //next数组当前i位置的数值可以结算了，就是currentNumber+1
        if (str[i - 1] == str[currentNumber]) {
            //++currentNumber一方面给当前 i 位置赋值，另一方面，i+1 位置正好用它
            next[i++] = ++currentNumber;
        } else if (currentNumber > 0) {//如果匹配失败，但currentNumber还能往前跳
            currentNumber = next[currentNumber];
        } else {//currentNumber到达0位置都没有匹配，则next信息为0，求下一位置
            next[i++] = 0;
        }
    }

    return next;
}