[TIOJ] 1497. 喝醉的宿主 The drunk host
題目連結: http://tioj.infor.org/problems/1497 本題是個裸後綴陣列題，基本上只要你懂它就寫得出來，不過我好像寫這題寫了一整天，倒最後是參考 這篇 的$O(n \log ^2 n)$的作法才刻了出來，不過後來還是有寫一份radix sort的版本，但效率不知為何很差就是了... $O(n \log ^2 n)$的作法 #include <bits/stdc++.h>
using namespace std;
#define N 100000
#define PB push_back
struct sfx{
int index;
int r,nr;
};
char str[N + 10];
int len;
int mapping[N + 10];
sfx sa[N + 10];
bool cmp(sfx a,sfx b){
if(a.r==b.r){
return a.nr<b.nr;
}else{
return a.r<b.r;
}
}
void SA();
int main(){
gets(str);
len = strlen(str);
SA();
for(int i=0;i<len;i++){
printf("%d\n",sa[i].index);
}
return 0;
}
void SA(){
for(int i=0;i<len;i++){
sa[i].index = i;
sa[i].r=str[i];
sa[i].nr=(i+1>=len)?-1:str[i+1];
}
sort(sa,sa+len,cmp)...