使用纯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;
}

上一篇:高精度数的运算问题


下一篇:C++ gbk与utf8互转