后缀数组(lcp)+st表-hdu4622

本文主要是介绍后缀数组(lcp)+st表-hdu4622，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

hdu4622
后缀数组基础题？

昨天学了后缀排序其实最有用的是后缀数组求 $l c p$ ？
用了一个 $h e i g h t [i] = l c p (s a [i], s a [i - 1])$ ，也就是排名为 $i$ 的和排名 $i - 1$ 的后缀的 $l c p$
为了方便，设 $h [i] = h e i g h t (r k [i])$ 就是 $i$ 位置的后缀和它前一名的后缀的 $l c p$

有几个性质：
$h[i]\ge h[i-1]+1$ ，证明可以感性理解一下，把 $i - 1$ 和它的上一名同时去掉第一位就是 $h [i]$
有了这个就可以快速求出 $h$ 数组：

inline void geth(){int j,k=0;for(int i=1;i<=n;i++){if(k) --k;j=sa[rk[i]-1];while(s[i+k]==s[j+k]) ++k;h[rk[i]]=k;}
}

还有 $lcp(i,j)=min_{i+1\le k\le j}(h[k])$
这个也可以感性理解一下，手动模拟之类的
有了这个就可以快速求出 $l c p$ ，这道题中套一个 $s t$ 表求区间最小值就好了

inline int query(int l,int r){int k=log2(r-l+1);return min(st[l][k],st[r-(1<<k)+1][k]);
}
//st表，区间min
inline int lcp(int l,int r){if(l>r) swap(l,r);return query(l+1,r);
}

然后再回来看这道题，区间 $[l, r]$ 本质不同的子串其实就是所有后缀的长度减去它和之前后缀的 $l c p$ ，因为它的 $l c p$ 是之前出现过的，然后后面每加一个字符就可以产生一个新的。
而且因为后缀排序的特性，不会出现某两个排名 $i, j, k (i < j < k)$ 且 $l c p (i, k) > l c p (j, k)$ ，所以这个方法是正确的

最后放代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define maxn 2005
using namespace std;inline int rd(){int x=0,f=1;char c=' ';while(c<'0' || c>'9') f=c=='-'?-1:1,c=getchar();while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();return x*f; 
} int t,n,m,q,sa[maxn],rk[maxn],tp[maxn],tax[maxn],h[maxn],st[maxn][12];
char s[maxn];inline void rsort(){for(int i=1;i<=m;i++) tax[i]=0;for(int i=1;i<=n;i++) ++tax[rk[i]];for(int i=1;i<=m;i++) tax[i]+=tax[i-1];for(int i=n;i;i--) sa[tax[rk[tp[i]]]--]=tp[i];
}
//基数排序 
inline void ssort(){for(int i=1;i<=n;i++) rk[i]=s[i],tp[i]=i;rsort();for(int w=1,p=0;p<n && w<=n;w<<=1,m=p){p=0;for(int i=n-w+1;i<=n;i++) tp[++p]=i;for(int i=1;i<=n;i++)if(sa[i]>w) tp[++p]=sa[i]-w;rsort();swap(rk,tp);rk[sa[1]]=p=1;for(int i=2;i<=n;i++)if(tp[sa[i]]==tp[sa[i-1]] && tp[sa[i]+w]==tp[sa[i-1]+w])rk[sa[i]]=p;else rk[sa[i]]=++p;}
}
//后缀排序 
inline void geth(){int j,k=0;for(int i=1;i<=n;i++){if(k) --k;j=sa[rk[i]-1];while(s[i+k]==s[j+k]) ++k;h[rk[i]]=k;}
}
//求h数组 
void prework(){for(int i=1;i<=n;i++) st[i][0]=h[i];for(int j=1;(1<<j)<n;j++)for(int i=1;i+(1<<j)-1<=n;i++)st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}inline int query(int l,int r){int k=log2(r-l+1);return min(st[l][k],st[r-(1<<k)+1][k]);
}
//st表，区间min
inline int lcp(int l,int r){if(l>r) swap(l,r);return query(l+1,r);
}
//求lcp，lcp(i,j)=min(h[k]) i+1<=k<=j 
inline int ask(int l,int r){vector<int> pos;for(int i=1;i<=n;i++)if(l<=sa[i] && sa[i]<=r) pos.push_back(sa[i]);int sum=r-pos[0]+1,tmp=sum;//sum：答案，tmp：当前后缀与之前所有后缀的lcp for(int i=1;i<pos.size();i++){int k=lcp(rk[pos[i]],rk[pos[i-1]]),len=r-pos[i]+1;//k当前与上一个的lcp tmp=min(tmp,k);//k<tmp,tmp一定=k tmp=max(tmp,min(k,r-pos[i-1]+1));//k>tmp,tmp可能为k,但不能超过上一个长度 sum+=len-min(tmp,len);}return sum;
}int main(){t=rd();while(t--){scanf("%s",s+1); n=strlen(s+1); m=127;ssort(); geth(); prework();q=rd();while(q--){int l=rd(),r=rd();if(l>r) swap(l,r);printf("%d\n",ask(l,r)); }}return 0;
}