//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

这里我还写了一个暴力破解的