[BZOJ4212]神牛的养成计划（trie+可持久化trie）

2019-11-06 07:04:00

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

这个tag好奇怪啊首先将字符串按照字典序排序，这样有相同前缀什么的串就到一起了然后依次将串插入一个trie，每一个点维护一下能匹配到这个点的串的左右端点然后将每个串反过来建立可持久化trie 对于每一个询问，首先在trie上匹配一下，看匹配到的左右端点是什么。然后在可持久化trie的这段区间中查找有多少个能匹配的后缀就行了时间是O(∑s) $O(/sum s)$ 的

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 2010000int 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); }}

上一篇：matlab基础学习一

下一篇：Struts2处理5种结果类型

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注