Description：

有一个两个串，然后从前往后枚举 $S$ 串字符往 $U$ 串里添加，若 $U$ 串后缀为 $T$ ，则去掉这个后缀继续流程，求最后的串。

$1\le len\le 1000000$

Solution：

考虑 $KMP$ 算法的过程，对于模板串，实际上就是每次在后面加一个字符并求出它的 $nxt$ 值，也即是说 $KMP$ 是支持在末尾加入，在末尾删除的，对于文本串，实际上也是每次加一个字符，然后和模板串匹配，所以也是支持末尾加入的，那就可以维护一个栈，记录在文本串匹配到某一位的时候，模板串匹配到了哪里，每次在上一次匹配的位置往后继续匹配，如果找到了，就弹 $l$ 次栈即可。

用 $KMP$ 算法的复杂度证明可以证明这是 $O(n)$ 的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define rint register int

#define MAXL 1000010

char s[MAXL],t[MAXL];

int l1,l2;

int nxt[MAXL];

int st[MAXL],p[MAXL],top = 0;

int main()

{

    scanf("%s%s",s + 1,t + 1);

    l1 = strlen(s + 1);l2 = strlen(t + 1);

    for(rint i = 2,j = 0;i <= l2;++i)

    {

        while(j && t[j + 1] != t[i])j = nxt[j];

        if(t[j + 1] == t[i])++j;

        nxt[i] = j;

    }

    for(rint i = 1;i <= l1;++i)

    {

        st[++top] = s[i];

        rint j = p[top - 1];

        while(j && s[i] != t[j + 1])j = nxt[j];

        if(s[i] == t[j + 1])++j;

        p[top] = j;

        if(p[top] == l2)top -= l2;

    }

    for(rint i = 1;i <= top;++i)putchar(st[i]);puts("");

    return 0;

}