2014-team1/kth_substring
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
// 求字符串str中第k大的互不相同的子串, 及其第一次出现的位置.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair <int, int> PII;
const int MN=2e5+7;
struct ST{
int mx[MN][20], log2[MN];
int n;
void init(int n, int a[]){
log2[0]=-1; this->n=n;
for (int i=1; i<=n; ++i) log2[i]=log2[i>>1]+1;
for (int i=0; i<n; ++i) mx[i][0]=a[i];
for (int j=1; (1<<j)<n; ++j){
for (int i=0; i+(1<<j)<=n; ++i){
mx[i][j]=min(mx[i][j-1], mx[i+(1<<(j-1))][j-1]);
}
}
}
int rmq(int a, int b){
if (a>b) swap(a,b);
int k=log2[b-a+1];
return min(mx[a][k], mx[b-(1<<k)+1][k]);
}
} AC,HI;
// AC用来求sa的rmq
// HI用来求height的rmq
//-----------------------后缀数组-----------------------
int T[MN],sa[MN],tsa[MN],rank[MN*2],trank[MN],c[MN],height[MN];
void bsort(int k,int n){
int i;
memset(c,0,sizeof(c));
for (i=0; i<n; i++) c[rank[i+k]]++;
for (i=1; i<n; i++) c[i]+=c[i-1];
for (i=n-1; i>=0; i--) tsa[--c[rank[i+k]]]=i;
memset(c,0,sizeof(c));
for (i=0; i<n; i++) c[rank[i]]++;
for (i=1; i<n; i++) c[i]+=c[i-1];
for (i=n-1; i>=0; i--) sa[--c[rank[tsa[i]]]]=tsa[i];
}
void getsa(int *T, int *sa, int n){
int i,k,p;
memset(rank,0,sizeof(rank));
memset(c,0,sizeof(c));
for (i=0; i<n; i++) c[T[i]]++;
for (i=1; i<max(n,128); i++) c[i]+=c[i-1];
for (i=n-1; i>=0; i--) sa[--c[T[i]]]=i;
rank[sa[0]]=p=1;
for (i=1; i<n; i++) rank[sa[i]]=(T[sa[i]]==T[sa[i-1]])?p:++p;
for (k=1; k<=n && p<n; k<<=1){
bsort(k,n);
trank[sa[0]]=p=1;
for (i=1; i<n; i++)
trank[sa[i]]=(rank[sa[i-1]]==rank[sa[i]] && rank[sa[i-1]+k]==rank[sa[i]+k])?p:++p;
for (i=0; i<n; i++) rank[i]=trank[i];
}
}
void getheight(int *T, int *sa, int *height, int n){
int i,j,k;
for (i=0; i<n; i++) rank[sa[i]]=i;
k=0; height[0]=0;
for (i=0; i<n; i++){
if (k) k--;
if (rank[i]==0) continue;
int j=sa[rank[i]-1];
while (i+k<n && j+k<n && T[i+k]==T[j+k]) k++;
height[rank[i]]=k;
}
}
//------------------------------------------------------
LL pre[MN];
void prefix(int n){
memset(pre,0,sizeof(pre));
for (int i=1; i<=n; i++) // Notice!
pre[i]=pre[i-1]+n-sa[i-1]-height[i-1];
} // 得到前缀和数组pre, 表示字典序小于等于"以sa[i]开头的后缀"的不同子串的个数.
inline int calc(int be,int len,int n){
int l=be,r=n-1;
while (l<r){
int mid=(l+r+1)>>1;
int tmp=HI.rmq(be,mid);
if (tmp<len) r=mid-1; else l=mid;
}
return l;
} // 二分当前子串可能出现的位置的范围, be为起始位置, len为子串长度, n为总的字符串长度
PII getk(LL k, int n){
int tmp=lower_bound(pre,pre+n,k)-pre-1;
int len=k-pre[tmp]+height[tmp];
int range=calc(tmp+1,len,n);
if (height[range]<len) range--;
int l=AC.rmq(tmp,range);
int r=l+len-1;
// 目标串是区间[tmp, range](sa字典序)内每个后缀的前缀
return PII(l,r);
} // 得到字典序第k大的子串在原串中第一次出现的位置, n为字符串长度
void startup(char str[],int n){
for (int i=0; i<n; i++) T[i]=str[i]-'a';
getsa(T,sa,n);
getheight(T,sa,height,n);
AC.init(n,sa);
HI.init(n,height);
prefix(n);
} // 需先调用该预处理函数, 其中n为字符串长度
/*
使用说明:
len=strlen(str);
startup(str, len);
PII rst=getk(k, len);
则字典序第k大的子串在字符串中最早出现的位置为[rst.first,rst.second]
*/
}}}// 求字符串str中第k大的互不相同的子串, 及其第一次出现的位置.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair <int, int> PII;
const int MN=2e5+7;
struct ST{
int mx[MN][20], log2[MN];
int n;
void init(int n, int a[]){
log2[0]=-1; this->n=n;
for (int i=1; i<=n; ++i) log2[i]=log2[i>>1]+1;
for (int i=0; i<n; ++i) mx[i][0]=a[i];
for (int j=1; (1<<j)<n; ++j){
for (int i=0; i+(1<<j)<=n; ++i){
mx[i][j]=min(mx[i][j-1], mx[i+(1<<(j-1))][j-1]);
}
}
}
int rmq(int a, int b){
if (a>b) swap(a,b);
int k=log2[b-a+1];
return min(mx[a][k], mx[b-(1<<k)+1][k]);
}
} AC,HI;
// AC用来求sa的rmq
// HI用来求height的rmq
//-----------------------后缀数组-----------------------
int T[MN],sa[MN],tsa[MN],rank[MN*2],trank[MN],c[MN],height[MN];
void bsort(int k,int n){
int i;
memset(c,0,sizeof(c));
for (i=0; i<n; i++) c[rank[i+k]]++;
for (i=1; i<n; i++) c[i]+=c[i-1];
for (i=n-1; i>=0; i--) tsa[--c[rank[i+k]]]=i;
memset(c,0,sizeof(c));
for (i=0; i<n; i++) c[rank[i]]++;
for (i=1; i<n; i++) c[i]+=c[i-1];
for (i=n-1; i>=0; i--) sa[--c[rank[tsa[i]]]]=tsa[i];
}
void getsa(int *T, int *sa, int n){
int i,k,p;
memset(rank,0,sizeof(rank));
memset(c,0,sizeof(c));
for (i=0; i<n; i++) c[T[i]]++;
for (i=1; i<max(n,128); i++) c[i]+=c[i-1];
for (i=n-1; i>=0; i--) sa[--c[T[i]]]=i;
rank[sa[0]]=p=1;
for (i=1; i<n; i++) rank[sa[i]]=(T[sa[i]]==T[sa[i-1]])?p:++p;
for (k=1; k<=n && p<n; k<<=1){
bsort(k,n);
trank[sa[0]]=p=1;
for (i=1; i<n; i++)
trank[sa[i]]=(rank[sa[i-1]]==rank[sa[i]] && rank[sa[i-1]+k]==rank[sa[i]+k])?p:++p;
for (i=0; i<n; i++) rank[i]=trank[i];
}
}
void getheight(int *T, int *sa, int *height, int n){
int i,j,k;
for (i=0; i<n; i++) rank[sa[i]]=i;
k=0; height[0]=0;
for (i=0; i<n; i++){
if (k) k--;
if (rank[i]==0) continue;
int j=sa[rank[i]-1];
while (i+k<n && j+k<n && T[i+k]==T[j+k]) k++;
height[rank[i]]=k;
}
}
//------------------------------------------------------
LL pre[MN];
void prefix(int n){
memset(pre,0,sizeof(pre));
for (int i=1; i<=n; i++) // Notice!
pre[i]=pre[i-1]+n-sa[i-1]-height[i-1];
} // 得到前缀和数组pre, 表示字典序小于等于"以sa[i]开头的后缀"的不同子串的个数.
inline int calc(int be,int len,int n){
int l=be,r=n-1;
while (l<r){
int mid=(l+r+1)>>1;
int tmp=HI.rmq(be,mid);
if (tmp<len) r=mid-1; else l=mid;
}
return l;
} // 二分当前子串可能出现的位置的范围, be为起始位置, len为子串长度, n为总的字符串长度
PII getk(LL k, int n){
int tmp=lower_bound(pre,pre+n,k)-pre-1;
int len=k-pre[tmp]+height[tmp];
int range=calc(tmp+1,len,n);
if (height[range]<len) range--;
int l=AC.rmq(tmp,range);
int r=l+len-1;
// 目标串是区间[tmp, range](sa字典序)内每个后缀的前缀
return PII(l,r);
} // 得到字典序第k大的子串在原串中第一次出现的位置, n为字符串长度
void startup(char str[],int n){
for (int i=0; i<n; i++) T[i]=str[i]-'a';
getsa(T,sa,n);
getheight(T,sa,height,n);
AC.init(n,sa);
HI.init(n,height);
prefix(n);
} // 需先调用该预处理函数, 其中n为字符串长度
/*
使用说明:
len=strlen(str);
startup(str, len);
PII rst=getk(k, len);
则字典序第k大的子串在字符串中最早出现的位置为[rst.first,rst.second]
*/