分析

有一道加强版的题解 这里 。那道题要求有多个模板串。而这道题只有一个，那么我们可以通过 来解决。考虑用栈储存路径，遇到完美匹配就返回 步。时间复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
char ch[N],S[N],ans[N];
int top = 0,nxt[N],f[N];
int main() {
    scanf("%s%s",ch + 1,S + 1);
    int n = strlen(S + 1);
    for(int i = 2,j = 0;i <= n;i++) {
        while(S[i] != S[j + 1] && j) j = nxt[j];
        if(S[i] == S[j + 1]) j++;
        nxt[i] = j;
    }
    int m = strlen(ch + 1);
    for(int i = 1,j = 0;i <= m;i++) {
        while(ch[i] != S[j + 1] && j) j = nxt[j];
        if(ch[i] == S[j + 1]) j++;
        ans[++top] = ch[i];
        f[top] = j;
        if(j == n) {top -= n;j = f[top];} 
    }
    for(int i = 1;i <= top;i++) printf("%c",ans[i]);
    printf("\n");
    return 0;
}