글 읽기 - 접미사배열(Suffix Array) 종만북 그대로 짰는데 결과가이상해요..

sgc109 7년 전 0

혹시라도 오타가 있을까봐 book.algospot.com 에도 들어가봤는데 한군데있길래 고쳤고

그외에 책이랑 아무리 비교해 봐도 다른 부분이없는데 결과가 생뚱맞게 나옵니다.. 어디가잘못된걸까요?

sort 를 하고난뒤에 바로 perm 벡터의 모든 원소를 출력하게 해서 디버깅을 해보니 애초에 처음 sort 의 결과부터가 잘못되던데

왜그러는걸까요..??

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
#include <stack>
#include <cstring>
#include <cstdlib>
#include <string>
#include <unordered_set>
#include <set>
#define REP(i,a,b) for(int i = a; i < b;++i) 
#define FOR(i,n) REP(i,0,n)
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> llll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int> > vvi;
typedef vector<ii> vii;
	
const int INF = 0x3a3a3a3a;
const int MAX_N = 1000000;

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[a];
		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(i,n) group[i] = s[i];
	group[n] = -1;

	vector<int> perm(n);
	FOR(i,n) perm[i] = i;
	FOR(i,n) printf("%d ",perm[i]);
	printf("\n");
	while(t < n) {
		Comparator compare(group,t);
		sort(perm.begin(), perm.end(),compare);
		FOR(i,n) printf("%d ",perm[i]);
		printf("\n");	
		t *= 2;
		if(t >= n) break;
		
		vector<int> newGroup(n+1);
		newGroup[n] = -1;
		newGroup[perm[0]] = 0;
		REP(i,1,n) {
			if(compare(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() {
	string s;
	cin >> s;
	getSuffixArray(s);
	return 0;
}

yukariko 7년 전 1

if(group[a] != group[b]) return group[a] < group[a];

group[a] < group[b] 로 바뀌어야 합니다.

sgc109 7년 전 0

@yukariko 으어 ㅠㅠㅠㅠㅠㅠ 정말 감사드립니다... 진짜 여러번계속봤는데도 발견도못했는데..ㅠㅠ 생각도 못한부분이라 대충훑어서그랬나보네요..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

접미사배열(Suffix Array) 종만북 그대로 짰는데 결과가이상해요..

sgc109 7년 전 0

yukariko 7년 전 1

sgc109 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말