#P4770 [NOI2018]你的名字的题解

题目背景

实力强大的小A 被选为了ION2018 的出题人，现在他需要解决题目的命名问题。

题目描述

小A 被选为了ION2018 的出题人，他精心准备了一道质量十分高的题目，且已经把除了题目命名以外的工作都做好了。

由于ION 已经举办了很多届，所以在题目命名上也是有规定的，ION 命题手册规定：每年由命题委员会规定一个小写字母字符串，我们称之为那一年的命名串，要求每道题的名字必须是那一年的命名串的一个非空连续子串，且不能和前一年的任何一道题目的名字相同。

由于一些特殊的原因，小A 不知道ION2017 每道题的名字，但是他通过一些特殊手段得到了ION2017 的命名串，现在小A 有Q 次询问：每次给定ION2017 的命名串和ION2018 的命名串，求有几种题目的命名，使得这个名字一定满足命题委员会的规定，即是ION2018 的命名串的一个非空连续子串且一定不会和ION2017 的任何一道题目的名字相同。

由于一些特殊原因，所有询问给出的ION2017 的命名串都是某个串的连续子串，详细可见输入格式。

输入格式

第一行一个字符串S ，之后询问给出的ION2017 的命名串都是S 的连续子串。第二行一个正整数Q，表示询问次数。接下来Q 行，每行有一个字符串T 和两个正整数l,rl,r，表示询问如果ION2017 的命名串是S [l..r]S[l..r]，ION2018 的命名串是T 的话，有几种命名方式一定满足规定。

输出格式

输出Q 行，第i 行一个非负整数表示第i 个询问的答案。

输入输出样例

输入

 scbamgepe

 smape

 sbape

 sgepe

输出

题解

分析

我们考虑对于一个询问，先求出TT中本质不同的子串个数，然后减去是S(l,r)S(l,r)子串的。

本质不同的子串个数，直接用height数组的性质就可以求。

我们考虑，对于TT的每一个后缀，求出其最长的前缀长度LL，使得该后缀长度为LL的前缀是S(l,r)S(l,r)的子串。

把SS和所有TT连起来建后缀数组。为了方便计算每个询问，我们用链表的方法，记录每个位置在同一个串中的前驱后继。

然后我们按顺序考虑TT的每一个后缀。

如果aa位置的后缀的满足条件的最长前缀为LL,，则a+1a+1位置的至少为L-1L−1。原理和求height数组相同，两边都同时去掉第一个字符，至少还留下L-1L−1。

所以考虑每个位置的话，用双指针扫描一下即可。

然后，假如我们现在考虑位置aa的长度为LL的前缀是否可行，就是相当于在SS的[l,r-L+1][l,r−L+1]内找一个位置bb，满足LCP(a,b)\geqslant LLCP(a,b)⩾L。

满足LCP(a,b)\geqslant LLCP(a,b)⩾L条件的在后缀数组上的区间[ll,rr][ll,rr]，可以二分，配合height数组的ST表在O(\log n)O(logn)的时间内求出。

然后问题转化为询问在后缀数组上的区间[ll,rr][ll,rr]内，是否存在一个在SS的[l,r-l+1][l,r−l+1]中的字符。这个问题可以用建主席树然后询问，单次查询时间复杂度O(\log n)O(logn)。

对于一个位置，它与后缀数组上一个位置可能会算重，所以要减掉它们的LCPLCP。由于两个位置可能不连续，这部分也要用ST表来查。

所以总时间复杂度O(n\log n)O(nlogn)。n=|S|+\sum|T|n=∣S∣+∑∣T∣。

代码

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define N 500505

 #define M 1800505

 #define reg register

 #define lg2(x)(31-__builtin_clz(x))

 typedef long long LL;

 int n,sa[M],height[M],x[M],s[M],mgk,bel[M],m,QL[N],QR[N],y[M],st[][M],nxt[M],head[N],node=,rt[M],pp[M],len[N];

 int ls[M*],rs[M*],sz[M*];

 char ss[N];

 bool isk;

 int _L,_R;

 void add(int&o,int pr,int l,int r,int pos){

     sz[o=++node]=sz[pr]+;

     if(l<r){

         const int mid=l+r>>;

         if(pos<=mid)add(ls[o],ls[pr],l,mid,pos),rs[o]=rs[pr];else add(rs[o],rs[pr],mid+,r,pos),ls[o]=ls[pr];

     }

 }

 void sort(){

     int m=mgk,c[M];

     for(int i=;i<=m;++i)c[i]=;

     for(int i=;i<=n;++i)++c[x[i]=s[i]];

     for(int i=;i<=m;++i)c[i]+=c[i-];

     for(int i=n;i;--i)sa[c[x[i]]--]=i;

     for(int k=,p;k<=n;k<<=){

         p=;

         for(int i=n-k+;i<=n;++i)y[++p]=i;

         for(reg int i=;i<=n;++i)if(sa[i]>k)y[++p]=sa[i]-k;

         for(reg int i=;i<=m;++i)c[i]=;

         for(reg int i=;i<=n;++i)++c[x[i]];

         for(reg int i=;i<=m;++i)c[i]+=c[i-];

         for(reg int i=n;i;--i)sa[c[x[y[i]]]--]=y[i];

         std::swap(x,y);

         x[sa[]]=p=;

         for(int i=;i<=n;++i)

         x[sa[i]]=y[sa[i]]==y[sa[i-]]&&y[sa[i]+k]==y[sa[i-]+k]?p:++p;

         if(p==n)break;

         m=p;

     }

     for(int i=,k=;i<=n;++i)

     if(x[i]>){

         k-=!!k;

         const int j=sa[x[i]-];

         while(s[i+k]==s[j+k])++k;

         height[x[i]]=k;

     }

 }

 inline int find(int l,int r){

     if(l>r)return n;

     const int lg=lg2(r-l+);

     return std::min(st[lg][l],st[lg][r-(<<lg)+]);

 }

 void init(){

     for(reg int i=;i<=n;++i)st[][i]=height[i];

     for(int i=;i<;++i)

     for(reg int j=;j<=n;++j)

     if(j+(<<i)<=n)st[i+][j]=std::min(st[i][j],st[i][j+(<<i)]);else break;

     int pre[N];

     memset(pre,,sizeof pre);

     for(int i=;i<=n;++i)

     if(s[sa[i]]<='z'){

         if(pre[bel[sa[i]]])

         nxt[pre[bel[sa[i]]]]=i,pp[i]=pre[bel[sa[i]]];else head[bel[sa[i]]]=i;

         pre[bel[sa[i]]]=i;

     }

 }

 void query(const int&ri,const int&le,int l,int r){

     if(sz[ri]==sz[le]||isk)return;

     if(_L<=l&&r<=_R)return(void)(isk=);

     const int mid=l+r>>;

     if(_L<=mid)query(ls[ri],ls[le],l,mid);

     if(mid<_R&&!isk)query(rs[ri],rs[le],mid+,r);

 }

 bool check(int pos,int len,int l,int r){

     int L,ll,rr;

     ll=,rr=pos-;

     while(ll<=rr){

         const int mid=ll+rr>>;

         if(find(mid+,pos)>=len)rr=mid-;else ll=mid+;

     }

     L=rr;

     ll=pos+,rr=n;

     while(ll<=rr){

         const int mid=ll+rr>>;

         if(find(pos+,mid)>=len)ll=mid+;else rr=mid-;

     }

     isk=;

     _L=l,_R=r;

     query(rt[ll-],rt[L],,n);

     return isk;

 }

 int main(){

     memset(bel,-,sizeof bel);

     mgk='z'+;

     scanf("%s",ss);

     for(int i=;ss[i];++i)

     s[++n]=ss[i],bel[n]=;

     s[++n]=mgk++;

     scanf("%d",&m);

     for(int i=;i<=m;++i){

         scanf("%s%d%d",ss,QL+i,QR+i);

         for(int j=;ss[j];++j)

         s[++n]=ss[j],bel[n]=i;

         len[i]=n;

         s[++n]=mgk++;

     }

     sort();

     init();

     for(reg int i=;i<=n;++i)

     if(!bel[sa[i]])add(rt[i],rt[i-],,n,sa[i]);else rt[i]=rt[i-];

     for(int i=;i<=m;++i){

         LL ans=len[i]-sa[head[i]]+;

         int mnid=sa[head[i]];

         for(int j=nxt[head[i]];j;j=nxt[j]){

             ans+=len[i]-sa[j]+;

             ans-=find(pp[j]+,j);

             mnid=std::min(mnid,sa[j]);

         }

         for(int j=mnid,L=mnid;s[j]<='z';++j){

             if(L<j)L=j;

             while(s[L]<='z'&&check(x[j],L-j+,QL[i],QR[i]-L+j))++L;

             if(x[j]!=head[i])ans-=std::max(L-j-find(pp[x[j]]+,x[j]),);else

             ans-=L-j;

         }

         printf("%lld\n",ans);

     }

     return ;

 }

巴特西

#P4770 [NOI2018]你的名字的题解

题目背景

题目描述

输入格式

输出格式

输入输出样例

输入

输出

题解

分析

代码

最新文章

热门文章

巴特西

#P4770 [NOI2018]你的名字 的题解

题目背景

题目描述

输入格式

输出格式

输入输出样例

输入

输出

题解

分析

代码

最新文章

热门文章

#P4770 [NOI2018]你的名字的题解