1 #include <bits/stdc++.h> 2 using namespace std; 3 static const int MAXN = 5e6 + 10; 4 bool vis[MAXN]; 5 char text[MAXN] = {‘\0‘}; 6 char pattern[MAXN] = {‘\0‘}; 7 char fuck[MAXN]; 8 int nxt[MAXN]; 9 int ans;10 void GetNext(char* s , int len)11 {12     int j;13     j = nxt[0] = -1;14     for(int i = 1 ; i < len ; ++i)15     {16         while(j != -1 && s[i] != s[j + 1])17             j = nxt[j];18         if(s[i] == s[j + 1])19             ++j;20         nxt[i] = j;21     }22 }23 void Kmp()24 {25     int n = strlen(text) , m = strlen(pattern);26     GetNext(pattern , m);27     int j = -1;28     for(int i = 0 ; i < n ; ++i)29     {30         while(j != -1 && text[i] != pattern[j + 1])31             j = nxt[j];32         if(text[i] == pattern[j + 1])33             ++j;34         if(j == m - 1)35         {36             vis[i - m + 1] = 1;37         }38     }39 }40 int main()41 {42     int t;43     scanf("%d" , &t);44     while(t--)45     {46         ans = 0;47         memset(nxt , 0 , sizeof(nxt));48         memset(vis , 0 , sizeof(vis));49         memset(pattern , ‘\0‘ , sizeof(pattern));50         memset(text , ‘\0‘ , sizeof(text));51         scanf(" %s" , text);52         scanf(" %s" , pattern);53         scanf(" %s" , fuck);54         Kmp();55         int n = strlen(text) , m = strlen(pattern);56         for(int i = 0 ; i < n ; )57         {58             if(vis[i])59             {60                 printf("%s" , fuck);61                 i += m;62             }63             else64             {65                 printf("%c" , text[i++]);66             }67         }68 69         printf("\n");70     }71 }