$$\newcommand{\Ord}{\mathcal{O}}$$

1497. 喝醉的宿主 The drunk host

連結:https://tioj.ck.tp.edu.tw/problems/1497

題目大意

給一個字串,求一個字串的Suffix Array。

題解

AC Code

使用 std::Sort

複雜度為$\Ord(|S|\log^2|S|)$

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
#include<bits/stdc++.h>
using namespace std;

vector<int> sa(string str)
{
int len = str.size();
vector<int> rank(len), sa(len), tmp(len);
for(int i=0;i<len;++i)
{
rank[i] = str[i];
sa[i] = i;
}
sort(sa.begin(), sa.end(), [&](int s, int e){
return rank[s]<rank[e];
});
for(int i=1;i<=len;i*=2)
{
auto val = [&] (int s) { return make_pair( rank[s], s+i<len?rank[s+i]:-1 ); };
sort(sa.begin(), sa.end(), [&](int s, int e){
return val(s) < val(e);
});
tmp[sa[0]]=0;
for(int j=1;j<len;++j)
if( val(sa[j]) == val(sa[j-1]) ) tmp[sa[j]] = tmp[sa[j-1]];
else tmp[sa[j]] = tmp[sa[j-1]] + 1;
rank.swap(tmp);
}
return sa;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
string str;

getline(cin, str);
for(int i:sa(str)) cout<<i<<'\n';
}

使用 Radix Sort

複雜度為$\Ord(|S|\log |S|)$

1
//TODO