相似子串 BZOJ 3230 字尾數組模闆題

時間2019 8 10——這題網上似乎找不到了，但是我有資料喲，大家可以下載下傳

附上連結https://download.csdn.net/my/uploads

這道題其實非常簡單，但是我場上并沒有想出來。。。。

現在拿出來補補智商

首先我們求出字尾數組sa[] height[] Rank[] 數組，到這我們的基本條件就已經具備了

然後再根據我們對字尾數組的了解：兩個排名不相鄰的最長公共字首定義為排名在它們之間的Height的最小值

RMQ問題當然首選ST表啊

那麼我們怎麼來獲得不同本質的子串呢？

把子串全部求出來是不可能的，這時候我們就又用到了字尾數組的height [] 數組

兩個排名相鄰的數組，它們的LCP以及其字首是肯定不能重複的，是以我們就隻需要記錄每一個字尾對不同本質子串的貢獻即可，即該字尾的長度減去LCP的長度，我們用一個num數組記錄貢獻的字首和，後面我們能使用二分(lowwer_bound)查找位置。

最後正反求最長公共前字尾的長度即可。

但是我傻逼，忘記了自己的sa[]數組記錄的是從0開始的位置、rank數組是紀錄第i位置字尾的排名。。。然後改了兩天都沒發現這個錯誤。。。。。

是我太菜了，不配寫題

如果我的題解看不懂：在這裡推薦另一個部落客的部落格，大家可以去膜拜一下https://www.cnblogs.com/yoyoball/p/9324662.html

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+7;
int len,m;
char str[maxn];
struct suf{
	int ST[maxn][20];
	int wa[maxn],wb[maxn],wv[maxn],wt[maxn];
	int r[maxn];
	int sa[maxn],height[maxn],Rank[maxn];
	ll num[maxn];//記錄每一個子字尾對子串的貢獻
	bool cmp(int *r,int a,int b,int l){
		return r[a]==r[b]&&r[a+l]==r[b+l];
	}
	void da(int n,int m){
		for(int i=0;i<len;i++) r[i]=str[i];
		r[len]=0;
		int i,j,p,*x=wa,*y=wb,*t;
		for(i=0;i<m;i++) wt[i]=0;
		for(i=0;i<n;i++) wt[x[i]=r[i]]++;
		for(i=1;i<m;i++) wt[i]+=wt[i-1];
		for(i=n-1;i>=0;i--) sa[--wt[x[i]]]=i;
		for(j=1,p=1;p<n;j*=2,m=p){
			for(p=0,i=n-j;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++) wt[i]=0;
			for(i=0;i<n;i++) wt[wv[i]]++;
			for(i=1;i<m;i++) wt[i]+=wt[i-1];
			for(i=n-1;i>=0;i--) sa[--wt[wv[i]]]=y[i];
			for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
				x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; 
		}
		calheight();
	}
	void calheight(){
		int i,j,k=0; 
		for( i=1;i<=len;i++ ) Rank[sa[i]]=i;  
		for(i=0;i<len;i++) {  
			if(k)k--;  
			int j=sa[Rank[i]-1];  
			while(r[i+k]==r[j+k]) k++; 
			height[Rank[i]]=k; 
		}     
		getnum();
		RMQ();
	}
	void getnum(){
		num[0]=0;
		for(int i=1;i<=len;i++)
			num[i]=num[i-1]+(len-sa[i]-height[i]);//先計算排名靠前的
							//先求得本身長度再減去與上一個排名的LCP即為對不同子串的貢獻
	}
	void RMQ(){
		for(int i=1;i<=len;i++)
			ST[i][0]=height[i];
		for(int i=1;(1<<i)<=len;i++)
			for(int j=len-(1<<i)+1;j>=1;j--)
				ST[j][i]=min(ST[j][i-1],ST[j+(1<<i-1)][i-1]);
	}
	int lcp(int x,int y){
		if (x==y) return len-sa[x];
        if (x>y) swap(x,y);
        ++x;
        int tmp=(int)(log(1.0*(y-x+1))/log(2.0));
        return min(ST[x][tmp],ST[y-(1<<tmp)+1][tmp]);//擷取兩個串的位置之間最小的最長公共字首，即這兩個串最多能比對到的最長公共字首
	}
	int query(ll x,ll y,int &edx,int &edy,int &lenx,int &leny){
		int posx,posy;
        posx=lower_bound(num+1,num+1+len,x)-num;
        posy=lower_bound(num+1,num+1+len,y)-num;//擷取字典序為x和為y的子串的字尾串所處的位置
		int ret=lcp(posx,posy);
		lenx=len-sa[posx]-(num[posx]-x);
        leny=len-sa[posy]-(num[posy]-y);//分别擷取兩個字串的長度
        edx=len-sa[posx]-lenx;
        edy=len-sa[posy]-leny;//兩個子串結尾的位置
        return min(ret,min(lenx,leny));//傳回能比對到的最長公共字首的長度
	}
	int query2(int stx,int sty,int lenx,int leny){
        int ret=lcp(Rank[stx],Rank[sty]);
        return min(ret,min(lenx,leny));
    }
}a[2];
void pre(){
    a[0].da(len+1,300);
	strrev(str);
    a[1].da(len+1,300);
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
    scanf("%d %d",&len,&m);
    scanf("%s",str);
	pre();
	// for(int i=1;i<=len;i++)
	// 	printf("%d: %d\n",i,a[0].sa[i]);
	while(m--){
		int tmp1,tmp2,edx,edy,lenx,leny;
		ll x,y;
		scanf("%lld %lld",&x,&y);
		if (x>a[0].num[len] || y>a[0].num[len])
			printf("-1\n");
		else {
			tmp1=a[0].query(x,y,edx,edy,lenx,leny);//正向
            tmp2=a[1].query2(edx,edy,lenx,leny);//反向
            printf("%lld\n",1LL*tmp1*tmp1+1LL*tmp2*tmp2);
		}
	}
return 0;
}