我是靠谱客的博主 潇洒汽车,最近开发中收集的这篇文章主要介绍串替换,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

题目描述

给出主串、模式串、替换串,用KMP算法找出模式串在主串的位置,然后用替换串的字符替换掉模式串

本题只考虑一处替换的情况,如果你想做的完美一些,能够实现多处替换那

可能需要考虑模式串和替换串长度不一致的情况

输入

 

第一个输入t,表示有t个实例

第二行输入第1个实例的主串,第三行输入第1个实例的模式串,第四行输入第1个实例的替换串

以此类推

 

输出

第一行输出第1个实例的主串

第二行输出第1个实例的主串替换后结果,如果没有发生替换就输出主串原来的内容。

以此类推

样例输入

3 aabbccdd bb ff aaabbbccc ddd eee abcdef abc ccccc

样例输出

aabbccdd aaffccdd aaabbbccc aaabbbccc abcdef cccccdef

 

#include <iostream>
#include <string>
using namespace std;
int *get_next(string s)
{
int *n=new int[s.length()];
n[0]=-1;
int i,j;
i=0;
j=-1;
while(i<s.length()-1)
{
if(j==-1 || s[i]==s[j])
{
i++;
j++;
n[i]=j;
}
else
j=n[j];
}
return n;
}
int KMP(string s,string key)
{
int *n=get_next(key);
int i=0,j=0;
int s_l=s.length(),j_l=key.length();
while(i<s_l && j<j_l)
{
if(j==-1 || s[i]==key[j])
{
i++;
j++;
}
else
{
j=n[j];
}
}
if(j==key.length())
return i-key.length()+1;
else
return 0;
}
int main()
{
string s,key,rekey;
int *n;
int t,temp;
cin>>t;
while(t--)
{
cin>>s>>key>>rekey;
cout<<s<<endl;
temp=KMP(s,key);
if(temp==0)
cout<<s<<endl;
else
{
s.erase(temp-1,key.size());
s.insert(temp-1,rekey);
cout<<s<<endl;
}
}
return 0;
}

 

最后

以上就是潇洒汽车为你收集整理的串替换的全部内容,希望文章能够帮你解决串替换所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(51)

评论列表共有 0 条评论

立即
投稿
返回
顶部