题目描述
给出主串、模式串、替换串，用KMP算法找出模式串在主串的位置，然后用替换串的字符替换掉模式串
本题只考虑一处替换的情况，如果你想做的完美一些，能够实现多处替换那
可能需要考虑模式串和替换串长度不一致的情况
输入
第一个输入t，表示有t个实例
第二行输入第1个实例的主串，第三行输入第1个实例的模式串，第四行输入第1个实例的替换串
以此类推
输出
第一行输出第1个实例的主串
第二行输出第1个实例的主串替换后结果，如果没有发生替换就输出主串原来的内容。
以此类推
输入样例1
3 aabbccdd bb ff aaabbbccc ddd eee abcdef abc ccccc
输出样例1
aabbccdd aaffccdd aaabbbccc aaabbbccc abcdef cccccdef
思路分析
题目说了两个点，一个是必用KMP，一个是只替换一处。
KMP关键求next值，求解next值的过程就是KMP。
next值似乎有两种模样，一种是从下标0开始的，next起始值为-1和0，另一种是从下标1开始的，next的起始值为0和1。
我课上学的是下标从1开始的，next【0】存的是子串的长度，下一个next值需要根据前一个next值来确定，首先判断当前字符的前面所组成的字符串的前后缀（前一个字符和第一个字符）是否是相同的字符，如果相同，那么当前字符的next值为前一个next值 1，如果不同，继续比较前一个字符和前一个next值所对应的字符是否相同，如果都不相同，那么next值为1。
利用KMP返回的子串的位置，使用replace函数，完事。
AC代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
int FindNext(string &str, int *next) {
next[0] = str.size();
next[1] = 0;
int i = 2, j = 0;
while (i <= next[0]) {
if (j == 0 || str[i - 2] == str[j-1]) {
next[i] = j 1;
i ;
j = next[i - 1];
} else j = next[j];
}
return 0;
}
int KMP(string &master, string &son, int *next) {
int i = 1, j = 1;
while (i<=master.size() &&j<=son.size()) {
if (j == 0 || master[i - 1] == son[j - 1]) {
i;
j;
} else j = next[j];
}
if (j > next[0])return i - next[0]-1;
return -1;
}
int main() {
int t;
cin >> t;
while (t--) {
string son, master,step_son;
cin >> master >> son>>step_son;
int next[son.size() 1];
FindNext(son, next);
cout<<master << endl;
if(KMP(master, son, next)!=-1)
master.replace(KMP(master, son, next),son.size(),step_son) ;
cout<<master<< endl;
}
}
