|
getNextArray（）： 输入一个要找的字符串，输出其Next数组。
getIndexOf（）： 输入两个字符串。在str1 中找str2，如果找到了，返回str2在str1中的开始位置。
#include<iostream>
#include<string>
using namespace std;
int* getNextArray(string str2){
if(str2.size() == 1){
int* next = new int[1];
next[0] = -1;
return next;
}
int* next = new int[str2.size()];
next[0] = -1;
next[1] = 0;
int i = 2;
// int cn = 0;
int cn = next[i-1];//被比较对象的下标位置
while(i < str2.size()){
if(str2[i-1] == str2[cn]){
next[i++] = ++cn;
}else if(cn > 0){
cn = next[cn];
}else{
next[i++] = 0;
}
}
//退出循环意味着数组已经填完了，
return next;
}
int getIndexOf(string str1, string str2){
if(str1.size() == 0 || str2.size() == 0)
return -1;
int i1 = 0;
int i2 = 0;
int* next = getNextArray(str2);
while(i1 < str1.size() && i2 < str2.size()){
if(str1[i1] == str2[i2]){
i1++;
i2++;
}else{
//当i2已经到了next的0位置，此时next【0】 值为-1,so 不用显示的指定i2=0了；
if(next[i2] == -1){
i1++;
}else{
i2 = next[i1];
}
}
}
return i2==str2.size()? i1-i2:-1;
}
int main(){
cout << getIndexOf("abcabcd","cab");
return 0;
}
| 
转播
