[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();
 }
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology