1 #include
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 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 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 else
64 {
65 printf("%c" , text[i++]);
66 }
67 }
68
69 printf("\n");
70 }
71 }