BOJ - 1701번 Cubeditor (C++, Python)

문제 출처: https://www.acmicpc.net/problem/1701

문제 난이도

Gold 2

문제 접근법

1. (메모리 초과) 모든 부분 문자열을 일일이 map에 넣어준 후(중복 x을 위함), 문자열에 해당 부분 문자열이 얼마나 있는지 count 한 후에 제일 긴 문자열을 출력했다.
2. KMP 알고리즘을 이용한다. 그 중, Failure 배열을 알면 풀 수 있는 문제 였다. 이에 관해 직접 공부하고 다시 풀어보는 것도 좋을 듯하다.

통과 코드

python

def make_table(pattern):
    table = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        while j > 0 and pattern[i] != pattern[j]:
            j = table[j-1]
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
    return max(table)


str = input()
ans = 0
for i in range(len(str)):
    ans = max(ans, make_table(str[i:len(str)]))

print(ans)

-> 채점을 무슨 19분 동안 함..

c++

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int make_table(string pattern) {
	vector<int> table(pattern.size(), 0);
	int j = 0;
	for (int i = 1; i < pattern.size(); i++) {
		while (j > 0 && pattern[j] != pattern[i]) j = table[j - 1];
		if (pattern[i] == pattern[j]) {
			j++;
			table[i] = j;
		}
	}
	int res = 0;
	for (int i = 0; i < table.size(); i++) {
		res = max(table[i], res);
	}
	return res;
}

int main() {
	string str;
	cin >> str;
	int ans = 0;
	for (int i = 0; i < str.size(); i++) {
		ans = max(ans, make_table(str.substr(i)));
	}
	cout << ans << "\n";
	return 0;
}

피드백

부분 문자열을 KMP 알고리즘으로 O(N+M) {N:기존 텍스트 사이즈, M:비교 문자 텍스트 사이즈}만에 비교가능하다는걸 기억해야겠다.
물론 다른 사람 코드와 KMP 알고리즘을 공부하고 짰지만, 아무것도 없이 짜라고 하면 기억이 안 날 것 같다.
j-1까지 맞으니깐 중간 점프~!를 통해 효율적으로 구한다는 것만 인지할 뿐.. 이해하기 좀 어렵다.