Method

• 显然题意是求 在s串中 将所有a串替换成c串,同时s,a,b串的长度均<=1e^6, 暴力求解很可能会TLE；
• 自然就想到KMP算法，找出a串的next数组，然后对s串进行匹配，将完全匹配处的首字符的下标用map进行维护，最后得到一个存有s串中所有完全匹配a串的位置的map；
• 输出时如果当前位置的map值为1，则输出b串，同时将指针后移|a|位，最终全部输出；

Code

#include <bits/stdc++.h>

using namespace std;
#pragma GCC optimize(2)
#define ll long long
const int Max = 1e6+3;
const int mod = 1e9+7;
template<typename T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

char s[Max], a[Max], b[Max];
int slen, alen, blen, next[Max];
map<int, int> mp;

void GetNext()
{
    next[0]=-1;

    int k=-1;
    int j=0;

    while(j<=alen-1){
        if(k==-1||a[j]==a[k]){
            k++;
            j++;
            next[j]=k;             
        }
        else k=next[k];
    }
}

void FindStr()
{    
    int i=0,j=0;
    while(i<slen)
    {
        if(j==-1||s[i]==a[j])
        {
            if(j==alen-1)
            {
                mp[i-j] = 1;
                j=next[j];
            }
            j++;
            i++;
        }else j=next[j];
    }
}

int main()
{
    scanf("%s%s%s", s, a, b);
    slen = strlen(s);
    alen = strlen(a);
    blen = strlen(b);
    GetNext();
    FindStr();
    for(int i=0; i<slen; i++)
    {
        if(mp[i]) {
            for(int j=0; j<blen; j++)
                printf("%c", b[j]);
            i = i + alen - 1;
        }
        else printf("%c", s[i]);
    }
    return 0;
}

蒟蒻一只，欢迎指正