完了我已经掉成Pupil了..
考虑对于每次询问做一个DP处理。
设$f(i,j,k)$表示使得串1的前i位，串2的前j位，串2的前k位能在主串中同时不相交出现的最短的前缀长度。
设$g(n,ch)$表示第n个字符之后，ch第一次出现的位置，如果不存在则设为$\infty$。
转移时考虑$f(i,j,k)=min(g([i\geq 1]f(i-1,j,k),S_1(i)),g([j\geq 1]f(i,j-1,k),S_2(j)),g([k\geq 1]f(i,j,k-1),S_3(k)))$。
边界条件$f(0,0,0)=0$。
可是这样单组询问复杂度是$O(250^3)$的，尽管这也是个常数。
但是注意到每组询问要么是追加一个字符，要么是删除末尾的字符。
假设在第i个串后追加一个字符，那么只需要把第i个串的DP数组推进一维即可。
删除第i个串末尾的字符，只需要把DP数组其他两维置INF。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <inttypes.h>
#include <cstring>
#include <assert.h>
#define debug(x) std::cout << #x << " = " << x << std::endl;
typedef long long int int_t;
using std::cin;
using std::endl;
using std::cout;
const int_t INF = 0x7fffffff;
const int_t LARGE = 250;
//µÚn¸ö×Ö·ûºó£¬×Ö·ûcµÚÒ»´Î³öÏÖµÄλÖÃ
int first[100001][26];
int dp[251][251][251];
int pos[4];
int strs[4][252];
char str[100010];
int n,m;
int at(int pos,char chr) {
#ifdef DEBUG
cout<<"at "<<pos<<" "<<chr<<" = ";
#endif
if(pos>n) {
#ifdef DEBUG
cout<<0x3f3f3f3f<<endl;
#endif
return 0x3f3f3f3f;
}
#ifdef DEBUG
cout<<first[pos][chr-'a']<<endl;
#endif
return first[pos][chr-'a'];
}
int main() {
// cin >> n >> m;
scanf("%d%d%s",&n,&m,str + 1);
memset(first[n],0x3f,sizeof(first[n]));
// cout<<first[n][1]<<endl;
for(int_t i = n; i >= 1; i --) {
memcpy(first[i-1],first[i],sizeof(first[i]));
first[i-1][str[i]-'a']=i;
}
#ifdef DEBUG
for(int i=0; i<n; i++) for(char chr='a'; chr<='d'; chr++) cout<<"first "<<i<<" "<<chr<<" = "<<first[i][chr-'a']<<endl;
#endif
memset(dp,0x3f,sizeof(dp));
dp[0][0][0]=0;
for(int i=1; i<=m; i++) {
static char opt[3];
int id;
scanf("%s%d",opt,&id);
if(opt[0]=='+') {
char chr,strx[3];
scanf("%s",&strx);
chr=strx[0];
strs[id][++strs[id][0]]=chr;
int len=strs[id][0];
if(id==1) {
// for(int i=0; i<=strs[1][0]; i++)
{
int i=strs[1][0];
for(int j=0; j<=strs[2][0]; j++) {
for(int k=0; k<=strs[3][0]; k++) {
if(i-1>=0) dp[i][j][k]=std::min(dp[i][j][k], at(dp[i-1][j][k],strs[1][i]));
if(j-1>=0) dp[i][j][k]=std::min(dp[i][j][k], at(dp[i][j-1][k],strs[2][j]));
if(k-1>=0) dp[i][j][k]=std::min(dp[i][j][k], at(dp[i][j][k-1],strs[3][k]));
#ifdef DEBUG
cout<<"dp "<<i<< " "<<j<<" "<<k<<" = "<<dp[i][j][k]<<endl;
#endif
}
}
}
} else if(id==2) {
for(int i=0; i<=strs[1][0]; i++) {
// for(int j=0; j<=strs[2][0]; j++)
int j=strs[2][0];
{
for(int k=0; k<=strs[3][0]; k++) {
if(i-1>=0) dp[i][j][k]=std::min(dp[i][j][k], at(dp[i-1][j][k],strs[1][i]));
if(j-1>=0) dp[i][j][k]=std::min(dp[i][j][k], at(dp[i][j-1][k],strs[2][j]));
if(k-1>=0) dp[i][j][k]=std::min(dp[i][j][k], at(dp[i][j][k-1],strs[3][k]));
#ifdef DEBUG
cout<<"dp "<<i<< " "<<j<<" "<<k<<" = "<<dp[i][j][k]<<endl;
#endif
}
}
}
} else {
for(int i=0; i<=strs[1][0]; i++) {
for(int j=0; j<=strs[2][0]; j++) {
int k=strs[3][0];
// for(int k=0; k<=strs[3][0]; k++)
{
if(i-1>=0) dp[i][j][k]=std::min(dp[i][j][k], at(dp[i-1][j][k],strs[1][i]));
if(j-1>=0) dp[i][j][k]=std::min(dp[i][j][k], at(dp[i][j-1][k],strs[2][j]));
if(k-1>=0) dp[i][j][k]=std::min(dp[i][j][k], at(dp[i][j][k-1],strs[3][k]));
#ifdef DEBUG
cout<<"dp "<<i<< " "<<j<<" "<<k<<" = "<<dp[i][j][k]<<endl;
#endif
}
}
}
}
} else {
if(id==1) {
for(int j=0; j<=strs[2][0]; j++)
for(int k=0; k<=strs[3][0]; k++) {
dp[strs[id][0]][j][k]=INF;
}
} else if(id==2) {
for(int i=0; i<=strs[1][0]; i++)
// for(int j=1;j<=strs[2][0];j++)
for(int k=0; k<=strs[3][0]; k++) {
dp[i][strs[2][0]][k]=INF;
}
} else {
for(int i=0; i<=strs[1][0]; i++)
for(int j=0; j<=strs[2][0]; j++) {
// for(int k=1;k<=strs[3][0];k++){
dp[i][j][strs[3][0]]=INF;
}
}
strs[id][0]--;
}
if(dp[strs[1][0]][strs[2][0]][strs[3][0]]<=n) {
printf("yes\n");
} else {
printf("no\n");
}
}
return 0;
}