本文主要是介绍B - 又见LKity（kmp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem Description
嗨！大家好，在TempleRun中大家都认识我了吧。我是又笨又穷的猫猫LKity。很高兴这次又与各位FZU的ACMer见面了。最近见到FZU的各位ACMer都在刻苦地集训，整天在日光浴中闲得发慌的我压力山大呀！于是，我准备为诸位编写一款小工具——LKity牌文本替换（众怒，：敢不敢更土点！）。这个小工具可以帮助诸位替换代码中的变量等功能，真心是一款编程，刷题必备的神器。其功能如下：
将给定的字符序列中所有包含给定的子串替换成另外一个给定的字符串。为了让其功能更加强大，替换过程中，将忽略大小写。并且不进行递归替换操作。
不过，作为笨笨的猫猫，我是心有余而力不足呀！希望诸位ACMer能帮我实现哈。（众FZU的ACMer：”……”）；
Input
输入包含多组数据。 输入为标准输入，输入包含3行。 第一行为需要查找的字符串S1。S1仅由大写或者小写字母组成，且其长度在区间[1，,100]内。 第二行为要替换的字符串S2。S2由[32,125]的字符组成，且其长度在区间[1,100]内。 第三行为原始字符串S，S由[32,125]的字符组成。且其长度在区间[1,50,000]内。
Output
对于每组数据，请输出替换后的字符串。
Sample Input
abc
bc ab
aaa aaabca 333Abcc##
Sample Output
aaa aabc aba 333bc abc##
#include <iostream>
#include <cstring>
#include <stdio.h>
#define M 150008
using namespace std;
int v[M];
void getnext(char *s1,int *next)
{
int m=strlen(s1);
next[0]=next[1]=0;
for(int i=1;i<m;i++)
{
int j=next[i];
while(j&&s1[i]!=s1[j])
j=next[j];
if(s1[i]==s1[j])
next[i+1]=j+1;
else
next[i+1]=0;
}
}
int kmp(char *s3,char *s1,int *next)
{
int n=strlen(s3);
int m=strlen(s1);
getnext(s1,next);
int j=0;
for(int i=0;i<n;i++)
{
while(j&&s1[j]!=s3[i])
j=next[j];
if(s1[j]==s3[i])
++j;
if(j==m)
v[i-m+1]=1;
}
}
int main()
{
char s1[M],s2[M],s3[M],s4[M];
int next[M];
while(~scanf("%[^\n] %[^\n] %[^\n] ",s1,s2,s3))
{
memset(v,0,sizeof(v));
int m=strlen(s1);
int n=strlen(s3);
strcpy(s4,s3);
for(int i=0;i<m;i++)
{
if(s1[i]>='A'&&s1[i]<='Z')
s1[i]+='a'-'A';
}
for(int i=0;i<n;i++)
{
if(s4[i]>='A'&&s4[i]<='Z')
s4[i]+='a'-'A';
}
kmp(s4,s1,next);
for(int i=0;i<n;i++)
{
if(v[i])
{
cout<<s2;
i+=m-1;
}
else
cout<<s3[i];
}
cout<<endl;
}
return 0;
}这篇关于B - 又见LKity（kmp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
