[NOI2011]阿狸的打字机

首先，可以发现这样一个性质
x在y中出现过=======y的某个前缀的后缀等于x。

先把AC自动机建出来后。
y的每一个前缀就是它在trie树上所遍历到的每一个点。
check这个点的后缀是否等于x也就是看沿着fail指针向上能否走到x。
这也就等价于这个点在x的子树中。
考虑去如何加速这个过程。
可以先把属于y的每一个点都先标记一下，对于询问x直接查询子树权值和即可。
综上，把询问按照y排序，在trie树上游走，进入一个点就给这个点+1，退出这个点就给这个点-1。
当走完y以后，处理所有关于y的询问。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 1100000
#define eps 1e-7
#define inf 1e9+7
#define ll long long
using namespace std;
inline int read()
{
	char ch=0;
	int x=0,flag=1;
	while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*flag;
}
queueq;
char ch[N];
int root=1,size=1,s[N],f[N],id[N],nxt[N][27];
struct edge
{
	int to;
	int nxt;
}e[N];
int num,head[N];
inline void add(int x,int y)
{
	e[++num]=(edge){y,head[x]};
	head[x]=num;
}
struct node
{
	int x,y,id;
}p[N];
bool cmp(node a,node b)
{
	return a.y