采用C++编程,字符串替换采用string数据类型实现
源代码如下:
#include <iostream> #include <string> using namespace std; void get_nextval(string T, int* nextval)//求模式串T的nextval函数值,并存入数组nextval { int i, j; i = 0;j = -1;nextval[0] = -1; while (T[i]) { if (j == -1 || T[i] == T[j]) { i++;j++; if (T[i] != T[j])nextval[i] = j; else nextval[i] = nextval[j];//若nextval后,字符与原位置相同,则再进行一次nextval算法 } else j = nextval[j]; } } int Findt1(string S, string t1, int i, int nextval[])//返回t1在S中出现的位置 { int k = 0; int x = k; while (S[i] && t1[x]) { if (k == -1 || S[i] == t1[k]) { i++;k++; } else k = nextval[k]; x = k; if (x == -1)//与nextval算法的一号位值冲突,估加x处理 { x = 0; } } if (!t1[k]) { return (i - k); } else { return -1; } } void Exchange(string& S, string t1, string t2, int i)//将找到的t1字符串替换成t2字符串 { int j = i + t1.length(); string a; string b; int k = 0; while (k < i) { a = a + S[k];k++; } k = 0; while (S[j]) { b = b + S[j];k++;j++; } S = a + t2; S = S + b; } int main() { int n = 0, i = 0; string S, t1, t2; cout << "请输入S:"; cin >> S; cout << "请输入t1:"; cin >> t1; cout << "请输入t2:"; cin >> t2; int x = t1.length(); int* nextval = new int[x];//为nextval数组分配空间 get_nextval(t1, nextval);//对t1求nextval值 i = Findt1(S, t1, i, nextval); while (i != -1)//若找到t1,则进行字符串替换 { Exchange(S, t1, t2, i); n++; i = Findt1(S, t1, i, nextval); } cout << S << endl << "替换次数n:" << n;//输出 }