struct SuffixArray
{
int id;ll rk;
bool operator<(const SuffixArray &b)const
{
return rk<b.rk;
}
}sa[__];
//rk[i]: s[i…n]的排名
//sa[i].id: 第i名为s[sa[i].id…n]
template<class T>
void get_sa(T s[],int n,int rk[])
{
for(int i=1;i<=n;i++)
sa[i].id=i,sa[i].rk=s[i];
for(int i=1;;i<<=1)
{
sort(sa+1,sa+1+n);
for(int j=1;j<=n;j++)
{
rk[sa[j].id]=rk[sa[j-1].id];
if(sa[j].rk!=sa[j-1].rk)
rk[sa[j].id]++;
}
if(rk[sa[n].id]==n)break;
for(int j=1;j<=n;j++)
{
sa[j].id=j;
sa[j].rk=1ll*rk[j]*__;
if(j+i<=n)
sa[j].rk+=rk[j+i];
}
}
}
//he[i]: 第i名后缀与第i-1名后缀的LCP
template<class T>
void get_he(T s[],int n,int rk[],int he[])
{
for(int i=1,cp=0;i<=n;i++)
{
if(cp)--cp;
int j=sa[rk[i]-1].id,maxx=max(i,j);
while(maxx+cp<=n && s[i+cp]==s[j+cp])
cp++;
he[rk[i]]=cp;//h[i]=cp;
}
}
Suffix Array
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- array_values返回数组中所有值array_keys返回数组所有的keyarray_search在数组中搜...
- 题目： Problem DescriptionOne day, Kaitou Kiddo had stolen a...
- 最近有在熟悉集合（数组）的一些操作方法。其中遇到判定一个元素是否存在于一个数组中的时候，了解到有这么三个方法。了解...
