「51nod 1647」小Z的trie

发表于

NOIP 编号为 ZJ-267 的小 Z 在 NOIP 中 AK 啦！

小 Z 打算去冲击省选，于是开始学习 trie 。

有一天，他得到了 NN 个字符串。

他先建立一个根节点，对于每一个字符串，他都从根节点开始一点点插入。

小 Z 不满足于此。他的大脑里盘旋着 MM 个问题：

如果给定一个二元组 (s,t)(s,t) （ ss，tt 都是 trie 中的节点且 ss 是 tt 的祖先），存在多少个二元组 (x,y)(x,y) （ xx，yy 都是 trie 中的节点且 xx 是 yy 的祖先），满足 ss ~ tt 路径上的字符串和 xx ~ yy 路径上的字符串完全一样？

注意 ss 可以等于 tt ， xx 也可以等于 yy 。

Constraints

1≤N,M≤1000001\leq N,M \leq 100000 ， 1≤sum≤10000001\leq sum \leq 1000000

Solution

先构建出 trie ，然后在 trie 上面建 sam。分别需要记录下原串的每个节点在 trie 上的位置和 trie 上的每个节点在 sam 上的位置。

对于一个询问，从 tt 对应在 sam 上面的节点开始，在 parent 树上跳直到深度最浅的满足节点对应长度不小于询问串的节点为止，该节点的 right 集合大小即为答案。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=1e6+5;
int n,m,p,l,r,cnt,length,head,tail;
int pos[N],spos[N],len[N];
char s[N];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
struct sam
{
	int size,root,len;
	int mx[N*2],fa[N*2],sz[N*2],ch[N*2][26];
	int c[N],id[N*2],f[N*2][21];
	sam()
	{
		size=root=1;
		memset(sz,0,sizeof(sz));
		memset(ch,0,sizeof(ch));
	}
	int ins(int c,int x)
	{
		int np=++size;mx[np]=mx[x]+1;
		len=max(len,mx[np]);sz[np]=1;
		while(x&&!ch[x][c])ch[x][c]=np,x=fa[x];
		if(!x)fa[np]=root;
		else
		{
			int y=ch[x][c];
			if(mx[y]==mx[x]+1)fa[np]=y;
			else
			{
				int nq=++size;
				memcpy(ch[nq],ch[y],sizeof(ch[y]));
				mx[nq]=mx[x]+1;
				fa[nq]=fa[y];fa[y]=fa[np]=nq;
				while(x&&ch[x][c]==y)ch[x][c]=nq,x=fa[x];
			}
		}
		return np;
	}
	void build()
	{
		for(int i=1;i<=size;i++)c[mx[i]]++;
		for(int i=1;i<=len;i++)c[i]+=c[i-1];
		for(int i=1;i<=size;i++)id[c[mx[i]]--]=i;
		for(int i=size;i>=1;i--)sz[fa[id[i]]]+=sz[id[i]];
		for(int i=1;i<=size;i++)
		{
			int x=id[i];f[x][0]=fa[x];
			for(int j=1;j<=20;j++)f[x][j]=f[f[x][j-1]][j-1];
		}
	}
	int find(int x,int len)
	{
		for(int i=20;i>=0;i--)
			if(mx[f[x][i]]>=len)x=f[x][i];
		return sz[x];
	}
}S;
struct node{int id,np;}t,q[N];
struct trie
{
	int sz,ch[N][26];
	trie(){sz=0;memset(ch,0,sizeof(ch));}
	void insert(char *s,int n)
	{
		int cur=0;
		for(int i=0;i<n;i++)
		{
			int c=s[i]-'a';
			if(!ch[cur][c])ch[cur][c]=++sz;
			cur=ch[cur][c];pos[++cnt]=cur;
		}
	}
	void bfs()
	{
		q[tail++]=(node){0,1};
		while(head!=tail)
		{
			t=q[head++];
			int u=t.id,last=t.np;
			for(int c=0;c<26;c++)
			{
				if(!ch[u][c])continue;
				int np=S.ins(c,last);
				spos[ch[u][c]]=np;
				q[tail++]=(node){ch[u][c],np};
			}
		}
	}
}T;
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s);
		length=strlen(s);
		len[i]=len[i-1]+length;
		T.insert(s,length);
	}
	T.bfs();S.build();
	m=read();
	while(m--)
	{
		p=read();l=read();r=read();
		printf("%d\n",S.find(spos[pos[r+len[p-1]]],r-l+1));
	}
	return 0;
}