题目描述
传送门
题解
这个tag好奇怪啊
首先将字符串按照字典序排序，这样有相同前缀什么的串就到一起了
然后依次将串插入一个trie，每一个点维护一下能匹配到这个点的串的左右端点
然后将每个串反过来建立可持久化trie
对于每一个询问，首先在trie上匹配一下，看匹配到的左右端点是什么。然后在可持久化trie的这段区间中查找有多少个能匹配的后缀就行了
时间是O(∑s)的
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define N 2010000
int n,q,la,len,l1,l2,sz,ans;
char a[N],s[N],s1[N],s2[N];
struct data{int st,ed;}loc[2005];
int trie[N][30],Max[N],Min[N],root[N];
struct Tire{int sum,ch[30];}tr[N];
int cmp(data a,data b)
{
int l=a.st,r=b.st;
while (l<=a.ed&&r<=b.ed)
{
if (s[l]<s[r]) return 1;
else if (s[l]>s[r]) return 0;
++l,++r;
}
if (l<=a.ed) return 0;
else if (r<=b.ed) return 1;
else return 0;
}
void insert(int &now,int l,int r)
{
tr[++sz]=tr[now];++tr[sz].sum;now=sz;
if (l>r) return;
int x=s[r]-'a';
insert(tr[now].ch[x],l,r-1);
}
int query(int L,int R,int now)
{
if (now==-1) return tr[R].sum-tr[L].sum;
int x=s2[now]-'a';
return query(tr[L].ch[x],tr[R].ch[x],now-1);
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;++i)
{
scanf("%s",a);la=strlen(a);
loc[i].st=len;
for (int j=0;j<la;++j) s[len++]=a[j];
loc[i].ed=len-1;
}
sort(loc+1,loc+n+1,cmp);
for (int i=1;i<=n;++i)
{
int now=0;
for (int j=loc[i].st;j<=loc[i].ed;++j)
{
int x=s[j]-'a';
if (!trie[now][x]) trie[now][x]=++sz;
now=trie[now][x];
if (!Min[now]) Min[now]=i;
Max[now]=max(Max[now],i);
}
}
sz=0;
for (int i=1;i<=n;++i)
{
root[i]=root[i-1];
insert(root[i],loc[i].st,loc[i].ed);
}
scanf("%d",&q);
for (int i=1;i<=q;++i)
{
scanf("%s",s1);scanf("%s",s2);l1=strlen(s1),l2=strlen(s2);
for (int j=0;j<l1;++j) s1[j]=(s1[j]-'a'+ans)%26+'a';
for (int j=0;j<l2;++j) s2[j]=(s2[j]-'a'+ans)%26+'a';
int now=0,l=-1,r=-1;
for (int j=0;j<l1;++j)
{
int x=s1[j]-'a';
if (!trie[now][x]) break;
now=trie[now][x];
if (j==l1-1) l=Min[now],r=Max[now];
}
if (l==-1&&r==-1)
{
ans=0;
PRintf("%d\n",ans);
continue;
}
ans=query(root[l-1],root[r],l2-1);
printf("%d\n",ans);
}
}
