题目链接
Prefix
Time Limit: 2000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 162 Accepted Submission(s): 56
Problem Description
Alice gets N strings. Now she has Q questions to ask you. For each question, she wanna know how many different prefix strings between Lth and Rth strings. It’s so easy right? So solve it!
Input
The input contains multiple test cases.
For each test case, the first line contains one integer N(1≤N≤100000). Then next N lines contain N strings and the total length of N strings is between 1 and 100000. The next line contains one integer Q(1≤Q≤100000). We define a specail integer Z=0. For each query, you get two integer L, R(0<=L,R<=N) Then the query interval [L,R] is [min((Z+L)%N,(Z+R)%N)+1,max((Z+L)%N,(Z+R)%N)+1]. And Z change to the answer of this query.
Output
For each question, output the answer.
Sample Input
3
abc
aba
baa
3
0 2
0 1
1 1
Sample Output
7
6
3
题目大意：给N个字符串，询问[L,R]内的字符串有多少个不相同的前缀。
这是一道主席树经典题，我们将所有的前缀哈希后，把它当成一个数字来看，然后每个位置会插入这些数字，然后再求区间内有多少个不同的数字。
在这里我用trie完成类似哈希的工作，相当于给每个前缀赋值了。然后陆续地把这些值插入主席树中。在插入时，如果当前数字没有在之前出现过，直接将该位置++，如果出现过，要把之前出现的位置–，再把当前位置++。这样主席树上存的信息就是所有的出现的不同的数字的出现的最后一个位置，那么查询[l,r]答案的时候，对第r棵主席树进行查询，以l为界，如果出现位置在l的左边，显然我们需要把这些值去掉，如果出现位置在l右边，这就是我们需要的值。统计起来即可。
注意一个位置会有很多前缀，那么线段树的长度不能以N为准，而以前缀的总个数为准。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<set>
#define maxn 100009
#define maxt 4000009
using namespace std;
int N;
char str[maxn];
int Hash[maxn];
struct node{
int ls,rs,count;
}tree[maxt];
struct TRIE{
int next[27];
int pos;
}trie[maxn+555];
int Next[maxn],root[maxn],LL[maxn];
int flag=0,RT=0,TOT=0,tot=0;
int insert(int i,int l,int r,int p,int z)
{
int j=++tot,mid=(l+r)/2;
tree[j]=tree[i];
if(l==r)
{
tree[j].count+=z;
return j;
}
if(p<=mid)
tree[j].ls=insert(tree[j].ls,l,mid,p,z);
else
tree[j].rs=insert(tree[j].rs,mid+1,r,p,z);
tree[j].count=tree[tree[j].ls].count+tree[tree[j].rs].count;
return j;
}
int solve(int i,int l,int r,int pos)
{
if(l==r)return tree[i].count;
int mid=(l+r)/2;
if(pos<=mid)
return tree[tree[i].rs].count+solve(tree[i].ls,l,mid,pos);
else
return solve(tree[i].rs,mid+1,r,pos);
}
void init()
{
tot=TOT=RT=flag=0;
memset(Hash,0,sizeof(Hash));
memset(Next,0,sizeof(Next));
memset(trie,0,sizeof(trie));
}
int main()
{
while(cin>>N)
{
init();
int i,j,k;
int last=0,num=0;
for(i=1;i<=N;i++)
{
scanf("%s",str);
int j=0,p=RT;
LL[i]=num+1;
while(str[j]!='\0')
{
num++;
if(trie[p].next[str[j]-'a']!=0)
p=trie[p].next[str[j]-'a'];
else
{
trie[p].next[str[j]-'a']=++TOT;
p=TOT;
trie[p].pos=++flag;
}
k=trie[p].pos;
j++;
if(Next[k]==0)
{
root[i]=insert(last,1,maxn,num,1);
Next[k]=num;
last=root[i];
}
else
{
root[i]=insert(last,1,maxn,Next[k],-1);
last=root[i];
root[i]=insert(last,1,maxn,num,1);
last=root[i];
Next[k]=num;
}
}
}
int ask=0;
int Z=0,l,r,x,y;
scanf("%d",&ask);
for(i=1;i<=ask;i++)
{
scanf("%d%d",&l,&r);
x=min((Z+l)%N,(Z+r)%N)+1;
y=max((Z+l)%N,(Z+r)%N)+1;
l=x;r=y;
Z=solve(root[r],1,maxn,LL[l]);
printf("%d\n",Z);
}
}
return 0;
}