library/jongman_suffixarray.cpp at master · yongwhan/library · GitHub

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

struct Comparator {
	const vector<int> &group;
	int t;
	Comparator(const vector<int> &_group, int _t) : group(_group), t(_t) {}
	bool operator () (int a, int b) {
		if(group[a]!=group[b]) return group[a]<group[b];
		return group[a+t]<group[b+t];
	}
};

vector<int> getSuffixArray(const string &s) {
	int n=s.size();
	int t=1;
	vector<int> group(n+1);
	for (int i=0; i<n; i++) group[i]=s[i];
	group[n]=-1;
	vector<int> perm(n);
	for (int i=0; i<n; i++) perm[i]=i;
	while(t<n) {
		Comparator compareUsing2T(group, t);
		sort(perm.begin(), perm.end(), compareUsing2T);
		t*=2;
		if(t>=n) break;
		vector<int> newGroup(n+1);
		newGroup[n]=-1;
		newGroup[perm[0]]=0;
		for (int i=1; i<n; i++)
			if(compareUsing2T(perm[i-1], perm[i]))
				newGroup[perm[i]]=newGroup[perm[i-1]]+1;
			else
				newGroup[perm[i]]=newGroup[perm[i-1]];
		group=newGroup;
	}
	return perm;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	return 0;
}