题意:将给定字符串中的特定子字符串替换成另外一个字符串。
思路:水题,KMP算法寻找字符串并替换
#include<cstdio> #include<cstring> #define MAXN 50005 bool v[MAXN]; void getFail(char *P,int *f) { int m=strlen(P); f[0]=f[1]=0; for(int i=1;i<m;++i) { int j=f[i]; while(j && P[i]!=P[j]) j=f[j]; f[i+1]=(P[i]==P[j]) ? j+1:0; } } void find(char *T,char *P,int *f)//n为T的长度 m为P的长度 { int n=strlen(T),m=strlen(P); getFail(P,f); int j=0; for(int i=0;i<n;++i) { while(j && P[j]!=T[i]) j=f[j]; if(P[j]==T[i]) ++j; if(j==m) v[i-m+1]=1; } } char T[MAXN],P[MAXN],To[MAXN],th[MAXN]; int f[MAXN]; int main() { while(~scanf("%[^\n] %[^\n] %[^\n] ",P,th,To)) { memset(v,0,sizeof(v)); strcpy(T,To); int m=strlen(P),n=strlen(T); for(int i=0;i<m;++i) if(P[i]>='A' && P[i]<='Z') P[i]+='a'-'A'; for(int i=0;i<n;++i) if(T[i]>='A' && T[i]<='Z') T[i]+='a'-'A'; find(T,P,f); for(int i=0;i<n;++i) if(v[i]){printf("%s",th);i+=m-1;} else putchar(To[i]); putchar('\n'); } }