algospot 말버릇 (문제 ID: HABIT) c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/HABIT

algospot.com :: HABIT

문자열이 주어졌을때, 해당 문자열의 부분 문자열중 k번 이상 등장하는 문자열을 '말버릇'이라고 한다.

가장 긴 말버릇의 길이를 구하는 문제이다.

 

먼저 주어진 배열의 접미사 배열들을 사전순으로 나열한다. 그리고 어떤 부분 문자열 X가 출현하는 위치가 K군데 있다고 하자.

X는 K개의 접미사의 접두사가 된다. 이들 접미사는 항상 앞서 사전순으로 정렬한 접미사 배열에 인접하게 정렬됬어야 한다.

 

	#include<iostream>
	#include<vector>
	#include<algorithm>
	using namespace std;
	// 각 접미사들의 첫 t글자를 기준으로 한 그룹 번호가 주어질 때,
	// 주어진 두 접미사를 첫 2*t글자를 기준으로 비교한다.
	// group[]은 길이가 0인 접미사도 포함한다.
	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){
	// 첫 t글자가 다르면 이들을 이용해 비교
	if (group[a] != group[b])return group[a] < group[b];
	// 아니라면 s[a+t...]와 s[b+t...]의 첫 t글자를 비교
	return group[a + t] < group[b + t];
	}
	};
	// 문자열 s의 접미사 배열을 계산
	vector<int> getSuffixArray(const string& s) {
	int n = s.size();
	// group[i]=접미사들을 첫 t글자를 기준으로 정렬했을 때, s[i...]가 들어가는 그룹 번호
	// t=1일 때는 정렬할 것 없이 s[i...]의 첫 글자로 그룹 번호를 결정
	vector<int> group(n+1);
	int t = 1;
	for (int i = 0; i < n; i++)
	group[i] = s[i];
	group[n] = -1;
	// 결과적으로 접미사 배열이 될 반환 값 perm
	// perm[i] = s의 부분 문자열들 중 s[i...]의 사전 순위
	vector<int> perm(n);
	for (int i = 0; i < n; i++)
	perm[i] = i;
	while (t < n) {
	// group[]은 첫 t글자를 기준으로 계산해 뒀다.
	// 첫 2t글자를 기준으로 perm을 다시 정렬
	Comparator compareUsing2T(group, t);
	sort(perm.begin(), perm.end(), compareUsing2T);
	// 2t 글자가 n을 넘는다면 이제 접미사 배열 완성
	t *= 2;
	if (t >= n)break;
	// 2t글자를 기준으로 한 그룹 정보를 만든다
	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;
	}
	// s[i...]와 s[j...]의 공통 접두사의 최대 길이를 계산
	int commonPrefix(const string& s, int i, int j) {
	int k = 0;
	while (i < s.size() && j < s.size() && s[i] == s[j]) {
	i++; j++; k++;
	}
	return k;
	}
	// k번 이상 출현하는 s의 부분 문자열 중 최대 길이를 찾는다.
	int longestFrequent(int k, const string& s) {
	vector<int> a = getSuffixArray(s);
	int ret = 0;
	for (int i = 0; i + k <= s.size(); i++)
	ret = max(ret, commonPrefix(s, a[i], a[i + k - 1]));
	return ret;
	}
	int main() {
	int testcase;
	cin >> testcase;
	while (testcase--) {
	int k;
	string s;
	cin >> k;
	cin >> s;
	cout << longestFrequent(k, s) << endl;
	}
	}

view raw algospot 말버릇 (문제 ID: HABIT).cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/20.%20string/HABIT.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2