首页 > 代码库 > [后缀数组+二分+rmq] hdu 5008 Boring String Problem
[后缀数组+二分+rmq] hdu 5008 Boring String Problem
有点小可惜这道题,当时整个思路都想到了,就是最后找最左下标的时候不会处理,
然后结束完发现直接暴力就可以了,想到了可是不敢写,10w个a直接就T了啊。。。
数据太弱了,敢写就过系列啊 T T。
然后希望有大神提供完美思路!
题意:
给一个字符串 然后n次询问
对于每一次询问给一个v
然后问第 l⊕r⊕v+1小的子串的区间 (⊕代表异或)
然后输出l r
这里的l r 就是上一次输出的l r 初始化是0 0
不存在输出0 0 如果多个 输出出现最早的。
对于每一次询问给一个v
然后问第 l⊕r⊕v+1小的子串的区间 (⊕代表异或)
然后输出l r
这里的l r 就是上一次输出的l r 初始化是0 0
不存在输出0 0 如果多个 输出出现最早的。
思路:
首先后缀数组就不说了,做完之后遍历height,没有重复的串的话,同一sa里面不同的长度就是排序了,小的在前。
所以开一个结构体ans存三个东西,l:初始位置,r:可用的第一个位置(因为会有重复的子串),s:这个下标内有多少名。
(声明:这里面的出现的不一定是最早的下标)
所以我们先通过二分 找到它是在哪个后缀的前缀,就是sa的下标。
然后通过暴力前后,rmq判断,找到最早出现的位置(就是这个 居然不超时!!)
代码:
#include"cstdlib" #include"cstdio" #include"cstring" #include"cmath" #include"stack" #include"algorithm" #include"iostream" using namespace std; #define N 300012 __int64 wa[N],wb[N],wv[N],wws[N]; __int64 sa[N],ra[N],v[N],height[N],used[N]; __int64 Log[N],dp[N][30]; char fuck[N],fu[N]; struct node { __int64 l,r,s; } ans[N]; __int64 cmp(__int64 *r,__int64 a,__int64 b,__int64 l) { return r[a]==r[b]&&r[a+l]==r[b+l]; } void da(__int64 n,__int64 m) { __int64 i,j,p,*x=wa,*y=wb; for(i=0; i<m; i++) wws[i]=0; for(i=0; i<n; i++) wws[x[i]=v[i]]++; for(i=1; i<m; i++) wws[i]+=wws[i-1]; for(i=n-1; i>=0; i--) sa[--wws[x[i]]]=i; for(j=1,p=1; p<n; j*=2,m=p) { for(i=n-j,p=0; i<n; i++) y[p++]=i; for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j; for(i=0; i<n; i++) wv[i]=x[y[i]]; for(i=0; i<m; i++) wws[i]=0; for(i=0; i<n; i++) wws[wv[i]]++; for(i=1; i<m; i++) wws[i]+=wws[i-1]; for(i=n-1; i>=0; i--) sa[--wws[wv[i]]]=y[i]; for(swap(x,y),p=1,i=1,x[sa[0]]=0; i<n; i++) x[sa[i]]=cmp(y,sa[i],sa[i-1],j)?p-1:p++; } return ; } void gethei(__int64 n) { __int64 i,j,k=0; for(i=1; i<=n; i++) ra[sa[i]]=i; for(i=0; i<n; i++) { if(k) k--; j=sa[ra[i]-1]; while(v[i+k]==v[j+k]) k++; height[ra[i]]=k; } return ; } void rmqinit(__int64 n) { __int64 i,j; __int64 m=Log[n]; for(i=1; i<=n; i++) dp[i][0]=height[i]; for(i=1; i<=m; i++) { for(j=1; j+(1<<i)-1<=n; j++) dp[j][i]=min(dp[j][i-1],dp[j+(1<<(i-1))][i-1]); } } __int64 lcp(__int64 a,__int64 b) { __int64 x=ra[a],y=ra[b]; if(x>y) swap(x,y); x++; __int64 m=Log[y-x+1]; return min(dp[x][m],dp[y-(1<<m)+1][m]); } int main() { while(scanf("%s",fuck)!=-1) { __int64 n; scanf("%I64d",&n); __int64 i; __int64 len=strlen(fuck); for(i=0; i<len; i++) v[i]=fuck[i]-'a'+2; v[len]=0; da(len+1,40); gethei(len); rmqinit(len); memset(ans,0,sizeof(ans)); for(i=1; i<=len; i++) { ans[i].l=sa[i]; // 初始位置,原串的下标 ans[i].r=sa[i]+height[i]; //可用的第一个位置 也就是去重了 ans[i].s=len-sa[i]-height[i]+ans[i-1].s; // 到i 已经有多少名了 } __int64 ansl,ansr; //输出答案 初始化0 ansl=ansr=0; while(n--) { __int64 xx; __int64 k,sb=-1,l,r,chang; scanf("%I64d",&xx); k=(ansl^ansr^xx)+1; //记得异或完加一 if(k>ans[len].s) //如果超出 说明不存在 直接输出 { puts("0 0"); ansl=ansr=0; continue; } l=1; r=len; while(l<=r) //二分位置 { __int64 mid=(l+r)/2; if(ans[mid].s>=k) { sb=mid; r=mid-1; } else l=mid+1; } ansl=ans[sb].l; ansr=ans[sb].r+(k-ans[sb-1].s-1); chang=ansr-ansl+1; //[ansl,ansr]就是子串了 但不一定是最早的,同时记录长度 __int64 x; x=sb-1; //向前遍历 while(x>=2 && lcp(sa[sb],sa[x])>=chang) { ansl=min(ansl,ans[x].l); //记录最小 x--; } x=sb+1; //向后遍历 while(x<=len && lcp(sa[sb],sa[x])>=chang) { ansl=min(ansl,ans[x].l); //记录最小 x++; } ansl=ansl+1; ansr=ansl+chang-1; printf("%I64d %I64d\n",ansl,ansr); } } return 0; }
[后缀数组+二分+rmq] hdu 5008 Boring String Problem
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。