[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);
	for(int j=2;j<=len;j*=2){
		int cnt=0;
		int rr = sa[0].r;
		sa[0].r=cnt;
		mapping[sa[0].index]=0;
		for(int i=1;i<len;i++){
			if(sa[i].r == rr && sa[i].nr == sa[i-1].nr){
				rr=sa[i].r;
				sa[i].r=cnt;
			}else{
				rr=sa[i].r;
				sa[i].r=++cnt;
			}
			mapping[sa[i].index]=i;
		}
		for(int i=0;i<len;i++){
			int nn = sa[i].index+j;
			sa[i].nr = (nn>=len)?-1:sa[mapping[nn]].r;
		}
		sort(sa, sa+len, cmp);
	}
}

---

$O(n \log n)$的作法

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96

#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; vector<sfx> srs[N + 10]; 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(); void radixSort(); 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)?0:str[i+1]; } radixSort(); for(int j=2;j<=len;j*=2){ int cnt=1; int rr = sa[0].r; sa[0].r=cnt; mapping[sa[0].index]=0; for(int i=1;i<len;i++){ if(sa[i].r == rr && sa[i].nr == sa[i-1].nr){ rr=sa[i].r; sa[i].r=cnt; }else{ rr=sa[i].r; sa[i].r=++cnt; } mapping[sa[i].index]=i; } for(int i=0;i<len;i++){ int nn = sa[i].index+j; sa[i].nr = (nn>=len)?0:sa[mapping[nn]].r; } radixSort(); } } void radixSort(){ int m = 0; for(int i=0;i<len;i++){ srs[sa[i].nr].PB(sa[i]); m=max(m,sa[i].nr); } int cnt=0; for(int i=0;i<=m;i++){ if(srs[i].empty())continue; for(auto j:srs[i]){ sa[cnt++] = j; } srs[i].clear(); } m = 0; for(int i=0;i<len;i++){ srs[sa[i].r].PB(sa[i]); m=max(m,sa[i].r); } cnt=0; for(int i=0;i<=m;i++){ if(srs[i].empty())continue; for(auto j:srs[i]){ sa[cnt++] = j; } srs[i].clear(); } }