[백준 / BOJ] 13506 카멜레온 부분 문자열

문제

출처 : www.acmicpc.net/problem/13506

13506번: 카멜레온 부분 문자열

카멜레온 부분 문자열이란, 문자열 S의 접미사이자 접두사인 부분문자열 T가 문자열S에서 한번 더 나오는 문자열을 말한다.

예를들어,

fixprefixsuffix에서 fix는 카멜레온 부분문자열인데, fix가 접두사, 접미사, 그리고 중간에 한번 더 나오기때문이다.

마찬가지로

abcabcabc또한 카멜레온 부분문자열이다.

문자열 S가 주어졌을때, 가장 긴 카멜레온 부분문자열을 찾는 문제다.

 

풀이

문자열의 길이가 10^6이기 때문에, 완전탐색으로 풀경우, 1000001* 50000 만큼 반복해서 시간초과가 난다. 

KMP알고리즘을 이용해 풀어야하는 문제였다.

 

KMP알고리즘의 희소배열을 만드는과정에서, 접두사와 접미사의 공통 부분문자열의 갯수를 알수있다. 예를들어,

ababcababab 와 같은 문자열이 주어지면,

희소배열은 

00120123434

와 같이 업데이트된다. 

여기서 굵은 글자를 보면, 접두사와 접미사가 4글자 연속으로 같은걸 알수있다.(abab)

 

이제 크게 3가지 경우를 봐주면된다.

접두사와 접미사를 제외하고 문자열에 한번더 공통으로 나오는 문자열을 카멜레온 문자열이라 하자

 

1. 접두사와 접미사, 카멜레온 문자열이 모두 떨어져 있는경우, 

abcabcabc

희소배열 : 0 0 0 1 2 3 1 2 3 

이 경우는 희소배열에서 같은 숫자를 찾아주면되는데, 희소배열에 업데이트되어있는 수가 앞에서부터 나오는 연속되는 패턴의 숫자를 표시해준것이므로, 희소배열에서 3을 찾아주고 출력해주면된다.

 

2. 접두사와 접미사가 겹쳐있어서 카멜레온 문자열을 알수없는경우

qwertyqwertyqwerty

희소배열 : 0 0 0 0 0 0  1 2 3 4 5 6 7 8 9 10 11 12

희소배열에 업데이트 되어있는 값을 기준으로 접두사, 접미사를 끊어서 보면

qwertyqwertyqwerty

qwertyqwertyqwerty

이렇게 나온다.

접두사와 접미사가 겹치는 부분이 카멜레온 문자열이 되는걸 알수있는데, 이게 항상성립하는게,

접두사와 접미사는 같은 패턴의 문자열이다. 즉, 이 두 패턴의 문자열이 겹치는 부분은 항상 같은 문자열이다. 따라서, 겹치는 부분이 최장 카멜레온 문자열이 되는것이다. 그래서 카멜레온 문자열은 다음과 같이 나온다.

qwertyqwertyqwerty

qwertyqwertyqwerty

qwertyqwertyqwerty

 

3. 접두사 혹은, 접미사가 떨어져있으면서 일정부분이 카멜레온 문자열이 되는경우 (이걸 못찾아서 계속 틀렸었음)

ababcabcabab

희소배열 : 0 0 1 2 0 1 2 0 1 2 3 4

희소배열의 마지막 수가 4로 업데이트 되어있는데, 남은 희소배열에서 4를 찾을수없고, 접두사와 접미사가 겹치는 부분이 없기때문에 카멜레온 문자열을 찾지못한다. 

마찬가지로 희소배열의 값을 기준으로 접두사, 접미사를 끊어보면,

ababcabcabab

이렇게 나온다. 이때 카멜레온 문자열을 찾기위해 접두사에서 접두사를 찾거나 접미사에서 접미사를 찾아주면된다.

접두사와 접미사가 같은게 보장되기때문에 둘중 한부분에서만 찾아주면되는데, 난 접두사에서 희소배열을 한번 더 만들어줬다.

접두사 : abab

희소배열 : 0 0 1 2

접두사와 접미사에서 공통으로 ab로 끊기는걸 알수있으므로 답은 ab가 된다.

 

소스코드 

https://github.com/devxb/JJUNalgo/blob/master/13506%20%EC%B9%B4%EB%A9%9C%EB%A0%88%EC%98%A8%20%EB%B6%80%EB%B6%84%20%EB%AC%B8%EC%9E%90%EC%97%B4/main.cpp

devxb/JJUNalgo