后缀数组
题目 后缀数组
思路分析
题意比较复杂
找到所有的后缀数组 然后按字典序排序 再比较得出两个相邻的最长公共前缀
最长公共前缀可能会想到用trie写 但是第一步有些似曾相识 如果用trie的话 又得把所有的后缀子串全都存一遍进去
考虑到这么复杂的操作 还是用字符串哈希来得快
所谓后缀数组
后缀不需要全存下来 只需要存第一个元素的指针即可
ponoiiipoi
10 i
9 oi
8 poi
7 ipoi
6 iipoi
5 iiipoi
4 oiiipoi
3 noiiipoi
2 onoiiipoi
1 ponoiiipoi
排序后得到 10 5 6 7……
再计算相邻的最长公共前缀 得到 0 1 2 1 0 0……
之前字典序排序用的是先求出最小表示法 但用字符串哈希了就没必要这样麻烦了
字典序排序不外乎就是一个字母一个字母比较 看第一个不一样的字母哪个更小就排前面
这个其实就是第三步也要做的——找最长公共前缀
找到最长公共前缀可以用二分 跟上题差不多思路 枚举下标 二分长度
找到最大公共前缀后 比较下一个元素的值 即可作排序
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N=300010,P=131;
char str[N];
ULL h[N],p[N];
int sa[N];
int n;
ULL find(int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
int get_MaxPreCommon(int a,int b){
int l=0,r=min(n-a+1,n-b+1);
while(l<r){
int mid=l+r+1>>1;
if(find(a,a+mid-1) == find(b,b+mid-1))
l=mid;
else
r=mid-1;
}
return r;
}
bool cmp(int a,int b){
int l=get_MaxPreCommon(a,b);
int anv=a+l>n ? INT_MIN : str[a+l];
int bnv=b+l>n? INT_MIN : str[b+l];
return anv<bnv;
}
int main()
{
cin>>str+1;
n=strlen(str+1);
p[0]=1;
for(int i=1;i<=n;i++){
h[i]=h[i-1]*P+str[i];
p[i]=p[i-1]*P;
sa[i]=i;
}
sort(sa+1,sa+1+n,cmp);
for(int i=1;i<=n;i++)
cout<<sa[i]-1<<" ";
cout<<endl;
for(int i=1;i<=n;i++)
{
if(i==1)
cout<<"0 ";
else
cout<<get_MaxPreCommon(sa[i-1],sa[i])<<" ";
}
return 0;
}
💬 评论