#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;
}