题解

#include<bits/stdc++.h>
using namespace std; 
 
const int N = 1000100; 
char s2[N], s1[N], s[N]; 
int nxt[N], sta[N], len, lenp; 
 
void getnext() {
    int i = 0, j = -1; 
    nxt[i] = j; 
    for (int i = 1 ; i < len ; i++) {
        while (j != -1 && s2[i] != s2[j + 1])j = nxt[j]; 
        if (s2[i] == s2[j + 1])++j; 
        nxt[i] = j; 
    }
}
 
void solve() {
    int top = 0; 
    for (int i = 0; i < len; i++) {
        int j = sta[top]; 
        s[++top] = s1[i]; 
        while (j != -1 && s2[j + 1] != s[top])j = nxt[j]; 
        if (s2[j + 1] == s[top])++j; 
        sta[top] = j; 
        if (sta[top] == lenp - 1) 
            top -= lenp; 
    }
    s[top + 1] = '\0'; 
    puts(s + 1); 
}
 
int main() {
    cin>>s1>>s2;
    len = strlen(s1), lenp = strlen(s2); 
    getnext(); 
    solve(); 
    return 0; 
}