题目链接：https://cn.vjudge.net/contest/281961#problem/D
题目大意：给你一个模式串，然后给你多个匹配串，匹配串的类型是包括可以覆盖的以及不可覆盖的。
具体思路：对于可以覆盖的字符串，我们就按照以前的方法来就行了，对于不可以覆盖的字符串，我们通过两个数组，一个是last和pos数组，对于不可覆盖的， 当前字符位置 - last[当前节点] <= pos[当前节点]。last数组记录的是当前这个字符串上次出现的位置。
AC代码：
#include<iostream>
#include<stack>
#include<stdio.h>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
# define ll long long
const int maxn = 2e5+;
const int maxm = 1e6+;
char str1[maxn],str2[maxn];
int tot,ch[maxn][];
int type[maxn],pos[maxn],node[maxn],val[maxn];
int fail[maxn],last[maxn],ans[maxn][];
void add(int t)
{
int p=;
int len=strlen(str2);
for(int i=; i<len; i++)
{
int u=str2[i]-'a';
if(!ch[p][u])
ch[p][u]=++tot;
p=ch[p][u];
pos[p]=i+;
}
node[t]=p;
val[p]=;
}
void getfail()
{
queue<int>q;
for(int i=; i<; i++)
{
if(ch[][i])
q.push(ch[][i]);
}
while(!q.empty())
{
int top=q.front();
q.pop();
for(int i=; i<; i++)
{
int u=ch[top][i];
if(u==)
continue;
q.push(u);
int v=fail[top];
while(v&&ch[v][i]==)
v=fail[v];
fail[u]=ch[v][i];
// last[u]=val[fail[u]] ? fail[u] : last[fail[u]];
}
}
}
void cal(int t,int i)
{
while(t)
{
ans[t][]++;
// cout<<i<<" "<<last[t]<<" "<<pos[t]<<endl;
if(i-last[t]>=pos[t])ans[t][]++,last[t]=i;
t=fail[t];
// break;
}
}
void getans()
{
memset(last,-,sizeof(last));
int len=strlen(str1);
int p=;
for(int i=; i<len; i++)
{
int u=str1[i]-'a';
while(p&&ch[p][u]==)
p=fail[p];
p=ch[p][u];
if(val[p])
cal(p,i);
else if(fail[p])
cal(fail[p],i);
}
}
void init(){
tot=;
memset(ch,,sizeof(ch));
memset(val,,sizeof(val));
memset(fail,,sizeof(fail));
memset(last,,sizeof(last));
memset(ans,,sizeof(ans));
}
int main()
{
// memset(last,-1,sizeof(last));
int n;
int Case=;
while(~scanf("%s",str1)){
init();
scanf("%d",&n);
for(int i=; i<n; i++){
scanf("%d %s",&type[i],str2);
add(i);
}
getfail();
getans();
printf("Case %d\n",++Case);
for(int i=; i<n; i++){
printf("%d\n",ans[node[i]][type[i]]);
}
printf("\n");
}
return ;
}