[C++] 알고스팟/접미사 배열 - 말버릇

문제 링크

https://algospot.com/judge/problem/read/HABIT

algospot.com :: HABIT

 

접미사 배열을 이용해서 푸는 문제입니다.

접미사 배열이란 문자열에서 나타날 수 있는 모든 접미사들을 사전순으로 정렬해 둔 배열을 말합니다.

 

banana 라는 문자열의 접미사는 아래와 같이 총 6개가 있습니다.

 

이 접미사들을 사전순으로 정렬을 하면 a가 가장 먼저오고 na가 가장 마지막에 오게됩니다.

이렇게 정렬된 각 접미사들의 전체 문자열 시작위치가 접미사 배열이 됩니다.

 

예시에서 접미사 a의 시작위치는 banana의 가장 마지막인 5가 되고

접미사 na의 시작위치는 4가 됩니다.

 

문제에서 부분 문자열이 k번 이상만큼 여러번 나오려면 항상 인접한 접미사들의 접두사로 나오게됩니다.

따라서 인접한 모든 접미사의 공통 접두사가 k번 이상 나오는지를 접미사 배열을 통해 확인하면 됩니다.

 

위에서 구한 접미사 배열을 순서대로 살펴보면

1번부터 3번까지의 접미사들의 접두사가 모두 a로 같기 때문에 s에서 가장 많이 나오는 부분 문자열이 됩니다.

 

문제 링크

 

	#include <iostream>
	#include <vector>
	#include <string>
	#include <algorithm>
	#define endl '\n'
	#define fastio cin.sync_with_stdio(false); cin.tie(nullptr)
	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;
	}
	//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 longestPrefix(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(){
	fastio;
	int _;
	cin >> _;
	while(_--){
	int k;
	string s;
	cin >> k >> s;
	cout << longestPrefix(k, s) << endl;
	}
	return 0;
	}

view raw habit.cpp hosted with ❤ by GitHub