这个题把病毒分为了两种，一种包含可以覆盖，另一种不可以，需要分别求出包含他们的个数，可以把两种都建在一颗tire树上，在最后求得时候判断一下当前节点是属于哪种字符串，如果是不包含的需要判断一下pre[i]+len[i]<=当前位置。
注意会有重复字符串，可以先map处理一下。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
#include<string>
#include<map>
using namespace std;
#define N 600110
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
const int child_num = ;
char vir[];
char s[N/];
int o[N/],len[N/],ans[N/][],po[N/];
int cc[N/];
map<string,int>f;
vector<int>ed[N/];
class AC
{
private:
int ch[N][child_num];
int fail[N];
int Q[N];
int val[N];
int sz;
int id[];
public:
void init()
{
fail[] = ;
for(int i = ;i < child_num ; i++)
id[i+'a'] = i;
}
void reset()
{
memset(ch[],,sizeof(ch[]));
memset(val,,sizeof(val));
sz = ;
}
void insert(char *a,int key)
{
int p = ;
for(; *a ; a++)
{
int d= id[*a];
if(ch[p][d]==)
{
memset(ch[sz],,sizeof(ch[sz]));
ch[p][d] = sz++;
}
p = ch[p][d];
}
val[p] = key;
}
void construct()
{
int i,head=,tail = ;
for(i = ; i < child_num ;i++)
{
if(ch[][i])
{
fail[ch[][i]] = ;
Q[tail++] = ch[][i];
}
}
while(head!=tail)
{
int u = Q[head++];
for(i = ; i < child_num ; i++)
{
if(ch[u][i])
{
fail[ch[u][i]] = ch[fail[u]][i];
Q[tail++] = ch[u][i];
}
else ch[u][i] = ch[fail[u]][i];
}
}
}
void work(int m,int kk,int g)
{
memset(ans,,sizeof(ans));
memset(po,-,sizeof(po));
int p = ,i,k = strlen(s);
for(i = ; i < k ; i++)
{
int d = id[s[i]];
p = ch[p][d];
int tmp = p;
while(tmp)
{
int v = val[tmp];
ans[v][]++;
if(po[v]+len[v]<=i)
{
po[v] = i;
ans[v][]++;
}
tmp = fail[tmp];
}
}
for(i = ; i <= g ; i++)
{
for(int j = ; j < ed[i].size() ; j++)
{
int v = ed[i][j];
if(o[v]) cc[v] = ans[i][];
else cc[v] = ans[i][];
}
}
printf("Case %d\n",kk);
for(i = ; i <= m ;i++)
printf("%d\n",cc[i]);
puts("");
}
}ac;
int main()
{
int i,m,kk=;
ac.init();
while(scanf("%s",s)!=EOF)
{
ac.reset();
f.clear();
scanf("%d",&m);
int g = ;
for(i = ; i <= m; i++)
ed[i].clear();
for(i = ;i <= m ;i++)
{
scanf("%d%s",&o[i],vir);
if(!f[vir])
{
f[vir] = (++g);
ac.insert(vir,g);
len[g] = strlen(vir);
}
ed[f[vir]].push_back(i);
}
ac.construct();
kk++;
ac.work(m,kk,g);
}
return ;
}