我现在感觉很淦
tag有个线段树
所以我先打了个线段树
突然发现字符串合并之后扫出来的位置不是在原串里的位置
然后就凉了

突然我灵机一动：
$folk$ ，链表干它！
$O(1)$ 更新链表，然后大力匹配，若匹配成功则删除然后重复操作

然后
$LG\;82pts\;\;LOJ\;87pts$
谷上又WA又TLE，loj上只WA（
下数据调试了$1h$
除了发现尼谷数据跟LOJ一样之外就啥也没查出来
调不动乐，求巨佬帮♂帮我

oh folk刚才发现了个申必问题
现在LOJ过了，谷TLE on #8(

求帮忙加速……

code:

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse4,mmx")
//焯，火车头死了（
#define ri register int
#define MAXN 1000005
#define g() getchar()
#define pc(a) putchar(a)
#define Tp template<typename T>
using namespace std;
const int inf=0x3f3f3f3f;

int lens,lent,nxt[MAXN];
int pre[MAXN],nst[MAXN];
char s[MAXN],t[MAXN];

inline void pres(){
    ri t1=0,t2=nxt[0]=-1;
    while(t1<lent)
    if(!(~t2)||t[t1]==t[t2])
    nxt[++t1]=++t2;
    else t2=nxt[t2];
}//KMP的预处理
inline void build(){
    for(ri i=0;i<lens;i++)
    pre[i]=i-1,nst[i]=i+1;
    pre[lens]=lens-1;
}//链表的预处理
inline void change(int l,int r){
    pre[nst[r]]=pre[l],nst[pre[l]]=nst[r];
}//删除链表上的区间
int sta=0;//每次遍历链表的起点
inline bool KMP(){
    ri t1=sta,t2=0;
    while(t1<lens&&t2<lent){
        if(!(~t2)||s[t1]==t[t2])
        t1=nst[t1],++t2;
        else t2=nxt[t2];
    }//在链表上跳着KMP
    if(t2==lent){
    	ri t=pre[t1];
        while(--t2) t=pre[t];//往前回溯，获取要删除的左确界
		change(t,pre[t1]); 
        if(t==sta) sta=t1;//防止串头被删了还从串头跳
        return false;
    }
    return true;//找不到匹配了，返回true结束
}

int main()
{
	scanf("%s %s",s,t);
    lens=strlen(s),lent=strlen(t);
    pres(),build();//预处理
    while(!KMP());//疯狂删
    ri i=sta; while(i<lens) pc(s[i]),i=nst[i];
    return 0;
}