[Baekjoon] 1701번 Cubeditor.cpp

[백준] 1701번 Cubeitor 문제 링크

완전탐색으로 쉽게 설계할 수 있는 문제이다. 하지만 그렇게 풀린다면 골드 3이 아니지. KMP 알고리즘을 활용하는 문제로, 추가적인 작업이 필요하다.

기본적으로 KMP 알고리즘은 접두사, 접미사 최대 일치 길이 테이블을 생성한다. 예를 들어 asdfasdf라는 문자열이 있다면 다음과 같은 접두사, 접미사 최대 일치 길이 테이블을 만들 수 있다.

이를 문제에 적용할 것이다. 접두사와 접미사가 일치한다는 것은 같은 문자열이 2번 반복된다는 것이므로 문제의 조건을 자동으로 충족한다. 문자열을 하나씩 늘려서 확인하기 때문에 부분 문자열에 대한 확인도 가능하다.

하지만 여기에 추가적으로 해주어야 할 것은 주어진 문자열을 탐색하는 시작 인덱스를 이동할 필요가 있다는 것이다. 예를 들어 abaaaaaa라는 문자열이 있다고 하자.

우리가 기대하는 것은 ab 뒤의 aaaaaa 라는 부분 문자열에서 aaaaa가 중복으로 일어나므로 5의 최대 일치 길이를 가져야 한다는 것이다. 최대 일치 길이 테이블을 생성할 때 문자열의 시작 인덱스를 0으로 고정하고 계산하기 때문에 모든 경우에 대한 검색이 불가능하다.

따라서, 최초에 주어진 문자열에 대해서만 최대 일치 길이를 계산할 것이 아니라 시작 인덱스를 하나씩 늘려가며 길이가 1씩 줄어든 문자열에 대해서도 최대 일치 길이를 계산할 필요가 있다.

이를 적용한 코드 전문은 아래와 같다.

#include <iostream>
#include <string>

std::string str;
std::string subStr;

int table[5001] = { 0, };

int maxLen = 0;

void make_table() {
	for (int index = 0; index < subStr.length(); index++) {
		table[index] = 0;
	}
	int start = 0;
	for (int end = 1; end < subStr.length(); end++) {
		while (start > 0 && subStr[start] != subStr[end]) {
			start = table[start - 1];
		}
		if (subStr[start] == subStr[end]) {
			table[end] = ++start;
			if (maxLen < table[end]) {
				maxLen = table[end];
			}
		}
	}
}

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

	std::cin >> str;

	for (int start = 0; start < str.length(); start++) {
		subStr = str.substr(start, str.length() - start);

		make_table();
	}

	std::cout << maxLen;
}