刚学后缀数组,写的十分丑陋的代码
大佬能否帮忙看一下哪里错了
或者是需要重构?
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
string s;
struct Node{
int id;
int x,y;
}Temp;
int getc(char c){
if(c>='0'&&c<='9')return int(c)-47;
if(c>='A'&&c>='Z')return int(c)-54;
if(c>='a'&&c<='z')return int(c)-60;
}
int x[70];
int rk[MAXN];
vector<Node> Tmp[MAXN];
vector<Node> ans;
int sa[MAXN];
int main(){
cin>>s;
int len=s.length();
for(int i=0;i<len;i++)x[getc(s[i])]++;
int cnt=0;
for(int i=1;i<=62;i++){
if(x[i])cnt++;
x[i]=cnt;
}
for(int i=0;i<len;i++){
rk[i]=x[getc(s[i])];
}
for(int k=1;k<=len;k*=2){
for(int j=0;j<len;j++){
Temp.id=j;
Temp.x=rk[j];
if(j+k<len)Temp.y=rk[j+k];
else Temp.y=0;
Tmp[Temp.y].push_back(Temp);
}
for(int i=0;i<=len;i++){
for(int j=0;j<Tmp[i].size();j++)ans.push_back(Tmp[i][j]);
Tmp[i].clear();
}
for(int i=0;i<ans.size();i++){
Tmp[ans[i].x].push_back(ans[i]);
}
ans.clear();
for(int i=0;i<=len;i++){
for(int j=0;j<Tmp[i].size();j++)ans.push_back(Tmp[i][j]);
Tmp[i].clear();
}
int num=1;
rk[ans[0].id]=1;
for(int i=1;i<ans.size();i++){
//cout<<ans[i].x<<" "<<ans[i].y<<endl;
if(ans[i].x!=ans[i-1].x||ans[i].y!=ans[i-1].y)num++;
rk[ans[i].id]=num;
}
ans.clear();
//for(int i=0;i<len;i++)cout<<rk[i]<<" ";
//cout<<endl;
}
for(int i=0;i<len;i++)sa[rk[i]]=i+1;
for(int i=1;i<=len;i++)cout<<sa[i]<<" ";
cout<<endl;
}