//KMP算法
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>using namespace std;//next數組值的推導void getNext(string &str, vector<int>& next){int strlong = str.size();//next數組的0位為0next[0]=0;//i為當前字符的位置，從1位（第2個開始）int i=1;//length為當前字符之前的最長匹配子串的長度int length=0;while(i<strlong){if(str[i]==str[length]){//cout<<"當前字符匹配"<<str[i]<<"和"<<str[length]<<endl;length++;next[i]=length;i++;}else{/*如果length為0，說明當前字符之前沒有匹配的子串，next數組值為0,i進一位*/if(length==0){//cout<<"當前字符之前沒有匹配的子串"<<endl;next[i]=0;i++;}/*如果length不為0，說明當前字符之前有匹配的子串，通過即查看上一個位置的最長匹配長度，繼續嘗試匹配*/else{//cout<<"當前字符之前有匹配的子串"<<endl;//查找這個字串之前得最長公共前后綴length=next[length-1];}}}
}//匹配
void insert(string &str, string &insert_str, vector<int>& next){cout<<"next數組為："<<endl;for(int a=0;a<next.size();a++){cout<<next[a]<<" ";}int i=0;int j=0;int num=0;while(i<str.size()){num++;cout<<"第"<<num<<"次匹配,匹配到原字符串的第"<<i<<"位"<<str[i] <<endl;if(str[i]==insert_str[j]){cout<<"第一項匹配成功"<<endl;i++;j++;if(j==insert_str.size()){cout<<"原字符串為："<<str<<endl;cout<<"匹配成功,從第"<<i-j+1<<"個字母開始"<<endl;cout<<"匹配內容為：";for(int k=i-j;k<i-j+insert_str.size();k++){cout<<str[k];}cout<<endl;cout<<"匹配次數為："<<num<<endl;return;}}else{if(j!=0){cout<<"匹配失敗，回溯至";j=next[j-1];cout<<"位置"<<j<<endl;cout<<str[i-j]<<"處"<<endl;}else{i++;}}}cout<<"匹配次數為："<<num<<endl;cout<<"匹配失敗"<<endl;}void violent(string str, string insert_str) {int i = 0; // 主串指針int j = 0; // 模式串指針int num = 0; // 匹配嘗試次數計數器while (i < str.size()) {num++;if (str[i] == insert_str[j]) {i++;j++;if (j == insert_str.size()) {// 成功匹配cout << "匹配成功" << endl;cout << "匹配子串為：";for (int k = i - j; k < i; k++) {cout << str[k];}cout << endl;cout << "匹配次數為：" << num << endl;return;}} else {i = i - j + 1; // 回退到本次匹配起始位置的下一個字符j = 0;         // 重置模式串指針}}// 匹配失敗cout << "匹配失敗" << endl;cout << "總共嘗試匹配次數為：" << num << endl;
}
int main(){string insert_str="aaad";vector<int> next(insert_str.size());getNext(insert_str,next);string str="daaaaaad";insert(str,insert_str,next);violent(str,insert_str);return 0;}

next即為需找位置得str的next

這里我還寫了一個暴力破解的

我們來分析一下次數是怎么來的

aaad的next為0120

如果是暴力算法，次數為1+4+4+4+4=17

1是因為第一項不符合直接過，4是因為我構造的是aaad，所以他每次都要判斷4次才能確定

如果是kmp，次數為1+4+2+2+2=11

在我們4比完后，j=2對應next數組為2，我們直接用2號位[第三個字母]去和之前p對應去比，

發現可以，那么值需要接著我往下比就好了，str的1，2字母無須比較，故為2，少比兩個