백준 1701. Cubeditor

tose33 2023. 2. 6. 15:48

1701번: Cubeditor

Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한

www.acmicpc.net

결론부터 말하면 이 문제는 KMP 알고리즘으로 푼다.

나는 kmp 알고리즘을 여기서 처음 봐서, 처음에 어떻게 풀까 고민하다가 이분탐색 생각이 났는데 시간복잡도 계산을 해보니 0.5초로는 아슬아슬하게 부족할것 같았다.

그런데 다른 생각이 안나서 일단 이분탐색으로 해봤는데 80퍼쯤에서 시간초과가 났다.

KMP 알고리즘은 어떤 문자열에 내가 찾는 특정 문자열이 몇개 존재하는지 판단하는 알고리즘이다.

이 문제는 kmp 의 응용인데, kmp 알고리즘은 접두, 접미가 일치하는 최대 길이를 pi 배열에 저장해놓고 문자열과 내가 찾는 문자열을 비교한 후에 pi 배열의 값을 토대로 문자들을 스킵할수 있다.

(자세한건 구글에 치면 자세히 나오니 찾아보자)

pi 배열에는 접두, 접미가 일치하는 최대 길이를 저장해 놓는다고 했다.

그런데 접두 접미가 일치한다는 것은 문자열이 두번 존재 한다는 것이므로 pi 배열의 값중 최댓값이 답이된다.

단 0부터 인덱스를 늘리면서 pi 배열을 만들어야 한다.

abcdabcabb 라면 abcdabcabb, abcdabcab, abcdabca, ... 이런식.