正題

---

題目大意

給出一個(gè)長(zhǎng)度為$n$的字符串，兩個(gè)串相似當(dāng)且僅當(dāng)可以通過(guò)每種字符置換使得它們相同。

$q$次詢問(wèn)這個(gè)字符串所有子串中和這個(gè)串中$s_{l,r}$子串有多少個(gè)相似的。

$1\le n\le 10^5,1\le q\le 5\times 10^5$

字符集是數(shù)字$0～9$

---

解題思路

請(qǐng)問(wèn)我是在陰間嗎

首先對(duì)于相似的比較相信很常見(jiàn)，維護(hù)每個(gè)數(shù)字上一個(gè)和它相同的數(shù)字的距離，然后沒(méi)有上一個(gè)就定為$0$就好了。

但是這題的問(wèn)題在于我們提取出區(qū)間構(gòu)成的數(shù)組時(shí)前面有些要變成$0$。

同樣的這也是個(gè)提示，因?yàn)樽址笮≈挥?0，我們也可以從這里入手，對(duì)于一個(gè)后綴，我們把第一個(gè)出現(xiàn)的數(shù)字的位置挖空后，我們至多會(huì)把這個(gè)后綴以這些位置分成$10$份，我們將這個(gè)字符串序列稱之為這個(gè)后綴的值。

然后我們需要的就是這些后綴值的“LCP”，而這樣我們需要我們能快速求這些后綴中字符串的LCP。

子串的LCP直接上SA+RMQ就好了。

這樣我們把弄出來(lái)的后綴的值排好序，然后維護(hù)一個(gè)相鄰的兩兩之間的"LCP"計(jì)入一個(gè)類似height的數(shù)組的東西。

然后對(duì)于詢問(wèn)我們就直接二分在RMQ上查詢就好了。

時(shí)間復(fù)雜度：$O(10n\log n+q\log n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int N=1e5+10; struct node{int l,r; }; struct nstr{vector<node> r;int id; }sr[N]; int n,m,q,nxt[10],p[10],pos[N]; int x[N],y[N],c[N],sa[N],rk[N]; int lg[N],f[N][20],h[N],s[N]; char rs[N]; void Qsort(){for(int i=1;i<=m;i++)c[i]=0;for(int i=1;i<=n;i++)c[x[i]]++;for(int i=1;i<=m;i++)c[i]+=c[i-1];for(int i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;return; } void Get_SA(){for(int i=1;i<=n;i++)x[i]=s[i]+1,m=max(m,s[i]+1),y[i]=i;Qsort();for(int w=1;w<=n;w<<=1){int p=0;for(int i=n-w+1;i<=n;i++)y[++p]=i;for(int i=1;i<=n;i++)if(sa[i]>w)y[++p]=sa[i]-w;Qsort();swap(x,y);x[sa[1]]=p=1;for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+w]==y[sa[i-1]+w])?p:(++p);if(p==n)break;m=p;}return; } void Get_Height(){int k=0;for(int i=1;i<=n;i++)rk[sa[i]]=i;for(int i=1;i<=n;i++){if(rk[i]==1)continue;if(k)k--;int j=sa[rk[i]-1];while(i+k<=n&&j+k<=n&&s[j+k]==s[i+k])k++;h[rk[i]]=f[rk[i]][0]=k;}return; } void Get_RMQ(){for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;for(int j=1;(1<<j)<=n;j++)for(int i=1;i+(1<<j)-1<=n;i++)f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);return; } int RMQ(int l,int r){if(!l||!r)return 0;if(l==r)return n-l+1;l=rk[l];r=rk[r];if(l>r)swap(l,r);l++;int z=lg[r-l+1];return min(f[l][z],f[r-(1<<z)+1][z]); } int RMQs(int l,int r){l++;int z=lg[r-l+1];return min(f[l][z],f[r-(1<<z)+1][z]); } void SA(){Get_SA();Get_Height();Get_RMQ();return; } int cp(node x,node y){//x<=yif(!x.l&&!y.l)return 2;if(!x.l)return 1;if(!y.l)return 0;int len=RMQ(x.l,y.l);if(len>x.r-x.l||len>y.r-y.l){if(x.r-x.l==y.r-y.l)return 2;return (x.r-x.l)<(y.r-y.l);}return s[x.l+len]<s[y.l+len]; } bool cmp(nstr x,nstr y){int i=0;while(1){if(i>=x.r.size())return 0;if(i>=y.r.size())return 1;int op=cp(x.r[i],y.r[i]);if(op==2)i++;else return op;}return 0; } int LCP(nstr x,nstr y){int i=0,ans=0;while(i<x.r.size()&&i<y.r.size()&&cp(x.r[i],y.r[i])==2)ans+=x.r[i].r-x.r[i].l+1,i++;if(i<x.r.size()&&i<y.r.size())ans+=min(RMQ(x.r[i].l,y.r[i].l),min(x.r[i].r-x.r[i].l,y.r[i].r-y.r[i].l)+1);return ans; } int main() { // freopen("similar.in","r",stdin); // freopen("similar.out","w",stdout); scanf("%d%d",&n,&q);scanf("%s",rs+1);for(int i=1;i<=n;i++){if(!nxt[rs[i]-'0'])s[i]=0;else s[i]=i-nxt[rs[i]-'0'];nxt[rs[i]-'0']=i;}SA();memset(nxt,0,sizeof(nxt));for(int i=n;i>=1;i--){nxt[rs[i]-'0']=i;for(int j=0;j<=9;j++)p[j]=nxt[j];sort(p,p+10);int now=i;for(int j=0;j<=9;j++){if(!p[j])continue;if(p[j]>now)sr[i].r.push_back((node){now,p[j]-1});sr[i].r.push_back((node){0,0});now=p[j]+1;}if(now<=n)sr[i].r.push_back((node){now,n});sr[i].id=i;}sort(sr+1,sr+1+n,cmp);for(int i=1;i<=n;i++)pos[sr[i].id]=i;for(int i=2;i<=n;i++)h[i]=LCP(sr[i-1],sr[i]);for(int i=2;i<=n;i++)f[i][0]=h[i];for(int j=1;(1<<j)<=n;j++)for(int i=1;i+(1<<j)-1<=n;i++)f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);int las=0;while(q--){int l,r;scanf("%d%d",&l,&r);l^=las;r^=las;if(l>n||r>n||l<1||r<1)continue;int x=pos[l],len=r-l+1;int L=x+1,R=n,ans=1;while(L<=R){int mid=(L+R)>>1;if(RMQs(x,mid)>=len)L=mid+1;else R=mid-1;}ans+=R-x;L=1;R=x-1;while(L<=R){int mid=(L+R)>>1;if(RMQs(mid,x)>=len)R=mid-1;else L=mid+1;}ans+=x-L;printf("%d\n",las=ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的YbtOJ-相似子串【SA,RMQ,二分】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。