http://www.tsinsen.com/ViewGProblem.page?gpid=A1484###
题解：
在线插入并不好做，我们将所有操作离线，变为删除操作。
每次询问的时候对于当前B串所在起始位置及其长度向上向下二分，然后查询区间内合法的当前A串内的匹配点即可。
用树状数组维护（不过我sb的写了线段树，后来才发现···）。
code：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 200005
using namespace std;
char ch,a[maxn*],b[maxn*],s[maxn];
int n,m,q,la,ra,lb,rb,lena,lenb,op[maxn],st[][maxn],ans[maxn];
int SA[maxn],rank[maxn],sum[maxn],height[maxn],t1[maxn],t2[maxn];
bool ok;
void read(int &x){
for (ok=,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=;
for (x=;isdigit(ch);x=x*+ch-'',ch=getchar());
if (ok) x=-x;
}
struct seg{
#define ls k<<1
#define rs (k<<1)+1
int val[maxn<<];
void build(int k,int l,int r){
if (l==r){
if (SA[l]<=ra) val[k]=;
return;
}
int m=(l+r)>>;
build(ls,l,m),build(rs,m+,r);
val[k]=val[ls]+val[rs];
}
void modify(int k,int l,int r,int x,int add){
if (l==r){val[k]+=add;return;}
int m=(l+r)>>;
if (x<=m) modify(ls,l,m,x,add);
else modify(rs,m+,r,x,add);
val[k]=val[ls]+val[rs];
}
int query(int k,int l,int r,int x,int y){
if (l==x&&r==y) return val[k];
int m=(l+r)>>;
if (y<=m) return query(ls,l,m,x,y);
else if (x<=m) return query(ls,l,m,x,m)+query(rs,m+,r,m+,y);
else return query(rs,m+,r,x,y);
}
}T;
void get_SA(){
int *x=t1,*y=t2,tot=; m=;
for (int i=;i<=n;i++) sum[x[i]=s[i]]++;
for (int i=;i<=m;i++) sum[i]+=sum[i-];
for (int i=n;i>=;i--) SA[sum[x[i]]--]=i;
for (int len=;tot<n;len<<=,m=tot){
tot=;
for (int i=n-len+;i<=n;i++) y[++tot]=i;
for (int i=;i<=n;i++) if (SA[i]>len) y[++tot]=SA[i]-len;
for (int i=;i<=m;i++) sum[i]=;
for (int i=;i<=n;i++) sum[x[y[i]]]++;
for (int i=;i<=m;i++) sum[i]+=sum[i-];
for (int i=n;i>=;i--) SA[sum[x[y[i]]]--]=y[i];
swap(x,y),x[SA[]]=tot=;
for (int i=;i<=n;i++){
if (y[SA[i]]!=y[SA[i-]]||y[SA[i]+len]!=y[SA[i-]+len]) tot++;
x[SA[i]]=tot;
}
}
for (int i=;i<=n;i++) rank[i]=x[i];
}
void get_height(){
for (int i=,j=;i<=n;i++){
if (rank[i]==) continue;
while (s[i+j]==s[SA[rank[i]-]+j]) j++;
height[rank[i]]=j;
if (j>) j--;
}
}
void prepare(){
for (int i=;i<=n;i++) st[][i]=height[i];
for (int i=;i<=;i++)
for (int j=;j<=n;j++){
st[i][j]=st[i-][j];
if (j+(<<(i-))<=n) st[i][j]=min(st[i][j],st[i-][j+(<<(i-))]);
}
T.build(,,n);
}
int calc(int l,int r){
if (l>r) swap(l,r);
int t=; l++;
if (l==r) return height[l];
for (;l+(<<t)<r;t++);
if (l+(<<t)>r) t--;
return min(st[t][l],st[t][r-(<<t)+]);
}
int find(int s,int x,int op){
int l,r,m;
if (op) l=s,r=n;else l=,r=s;
while (l!=r){
m=((l+r)>>)+op;
if (calc(m,s)<x){
if (op) r=m-;
else l=m+;
}
else{
if (op) l=m;
else r=m;
}
}
return l;
}
int query(){
int x=find(rank[lb],rb-lb+,),y=find(rank[lb],rb-lb+,);
return T.query(,,n,x,y);
}
int main(){
scanf("%s%s",a+maxn,b+maxn);
la=ra=maxn,lb=rb=maxn;
for (;a[ra];ra++); ra--;
for (;b[rb];rb++); rb--;
read(q);
for (int i=;i<=q;i++){
read(op[i]);
if (op[i]==) a[--la]=getchar();
else if (op[i]==) a[++ra]=getchar();
else if (op[i]==) b[--lb]=getchar();
else if (op[i]==) b[++rb]=getchar();
}
for (int i=la;i<=ra;i++) s[++n]=a[i];
lena=ra-la+,la=,ra=lena;
s[++n]='#';
int tmp=n+;
lenb=rb-lb+;
for (int i=lb;i<=rb;i++) s[++n]=b[i];
lb=tmp,rb=lb+lenb-;
get_SA(),get_height(),prepare();
for (int i=;i<lenb;i++) T.modify(,,n,rank[ra--],-);
for (int i=q;i>=;i--){
if (op[i]==) T.modify(,,n,rank[la++],-);
else if (op[i]==) T.modify(,,n,rank[ra--],-);
else if (op[i]==) T.modify(,,n,rank[++ra],),lb++;
else if (op[i]==) T.modify(,,n,rank[++ra],),rb--;
else ans[i]=query();
}
for (int i=;i<=q;i++) if (op[i]==) printf("%d\n",ans[i]);
return ;
}