题目大概是给一个主串，询问若干个模式串出现次数，其中有些模式串要求不能重叠。
对于可以重叠的就是一个直白的多模式匹配问题；而不可重叠，在匹配过程中贪心地记录当前匹配的主串位置，然后每当出现一个新匹配根据记录的位置判断这个新匹配是否成立，最后更新位置。
另外，考虑到数据可以出现多个模式串相同的情况，实现要做一些处理：
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define MAXN 666666
//-1 none, 0 overlap, 1 not, 2 both
int tn,ch[MAXN][],fail[MAXN],flag[MAXN],len[MAXN];
int insert(char *s,int k){
int x=,l=;
for(int i=; s[i]; ++i){
int y=s[i]-'a';
if(ch[x][y]==) ch[x][y]=++tn;
x=ch[x][y];
++l;
}
len[x]=l;
if(flag[x]==-) flag[x]=k;
else if(flag[x]== && k==) flag[x]=;
else if(flag[x]== && k==) flag[x]=;
return x;
}
void getfail(){
memset(fail,,sizeof(flag));
queue<int> que;
for(int i=; i<; ++i){
if(ch[][i]) que.push(ch[][i]);
}
while(!que.empty()){
int x=que.front(); que.pop();
for(int i=; i<; ++i){
if(ch[x][i]){
que.push(ch[x][i]);
fail[ch[x][i]]=ch[fail[x]][i];
}else ch[x][i]=ch[fail[x]][i];
}
}
}
int last[MAXN],ans[][MAXN],first[],second[];
char str[];
void query(){
int x=;
for(int i=; str[i]; ++i){
int y=str[i]-'a';
int tmp=x=ch[x][y];
while(tmp){
if(flag[tmp]!=- && flag[tmp]!=) ++ans[][tmp];
if(flag[tmp]!=- && flag[tmp]!=){
if(last[tmp]==- || i-last[tmp]>=len[tmp]){
last[tmp]=i;
++ans[][tmp];
}
}
tmp=fail[tmp];
}
}
}
int main(){
int n,cse=;
char s[];
while(~scanf("%s",str)){
tn=;
memset(ch,,sizeof(ch));
memset(flag,-,sizeof(flag));
scanf("%d",&n);
for(int i=; i<n; ++i){
scanf("%d%s",&first[i],s);
second[i]=insert(s,first[i]);
}
getfail();
memset(ans,,sizeof(ans));
memset(last,-,sizeof(last));
query();
printf("Case %d\n",++cse);
for(int i=; i<n; ++i){
printf("%d\n",ans[first[i]][second[i]]);
}
putchar('\n');
}
return ;
}