[백준] 1701 Cubeditor

백준 1701 Cubeditor

• https://www.acmicpc.net/problem/1701

접미사 배열 이용 풀이

• 코드 길이: 1940B
  시간: 16ms

• 어떤 문자열에서 두 번 이상 나오는 부분 문자열 중 가장 긴 길이
  = 각 접미사에 대해 접미사 배열에서 자기 앞에 오는 배열과 최장 공통 접두사의 길이 중 최댓값

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

//각 접미사들의 첫 t 글자를 기준으로 한 그룹 번호가 주어질 때
//주어진 두 접미사를 첫 2t 글자를 기준으로 비교한다
//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) {
		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);
	group[n] = -1;

	for (int i = 0; i < n; ++i)
		group[i] = s[i];

	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;

		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 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;
}

//중복되는 부분 문자열의 길이 줄 가장 긴 길이 반환
int longestCommonSubstring(const string& s) {
	vector<int> a = getSuffixArray(s);

	int ret = 0;
	for (int i = 0; i < a.size(); ++i) {
		int cp = 0;
		if (i > 0) cp = commonPrefix(s, a[i - 1], a[i]);
	
		ret = max(ret, cp);
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string s;
	cin >> s;

	cout << longestCommonSubstring(s);

	return 0;
}

KMP 알고리즘 이용 풀이

• 코드 길이: 943B
  시간: 96ms

• 어떤 문자열에서 두 번 이상 나오는 부분 문자열 중 가장 긴 길이
  = 문자열 S의 모든 접미사 S[i..]의 부분 일치 테이블에서의 최대 값

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;


vector<int> getPartialMatch(const string& N) {
	int m = N.size();
	vector<int> pi(m, 0);

	int begin = 1;
	int matched = 0;
	while (begin + matched < m) {
		if (N[matched] == N[begin + matched]) {
			++matched;
			pi[begin + matched - 1] = matched;
		}
		else {
			if (matched == 0) ++begin;
			else {
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}
	return pi;
}

int getLongestPatialMatch(const string& s) {
	
	int ret = 0;

	//s[i..]에 대해 부분 일치 테이블 계산
	for (int i = 0; i < s.size(); ++i) {
		vector<int> pi = getPartialMatch(s.substr(i));

		for (int j = 0; j < pi.size(); ++j) {
			ret = max(ret, pi[j]);
		}
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string s;
	cin >> s;
	cout << getLongestPatialMatch(s);

	return 0;
}

📌참고자료

• 백준 1701 Cubeditor 풀이
  https://zoomkoding.github.io/%EB%B0%B1%EC%A4%80/2019/09/17/baekjoon-1701.html