백준 13506 - 카멜레온 부분 문자열

문제 링크 : https://www.acmicpc.net/problem/13506

 

문제

문자열 S의 부분 문자열 T 중에서, 접두사(Prefix)도 될 수 있고, 접미사(Prefix)도 될 수 있고, 두 경우가 아닌 위치에도 등장하는 T를 카멜레온 부분 문자열이라고 한다.

문자열 S가 주어졌을 때, 카멜레온 부분 문자열을 구하는 프로그램을 작성하시오.

예를 들어, S = "fixprefixsuffix"와 같은 경우에는 "fix"는 접두사, 접미사도 되고, 두 경우가 아닌 위치에도 등장하는 부분 문자열로도 등장한다.

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져있으며, 길이는 106을 넘지 않는 자연수이다.

출력

가능한 카멜레온 부분 문자열 T 중에서 길이가 가장 긴 것을 출력한다. 만약, T가 존재하지 않으면 -1을 출력한다.

풀이 과정

https://readytojoin.tistory.com/entry/KMP-%EB%AC%B8%EC%9E%90%EC%97%B4-%EB%A7%A4%EC%B9%AD-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

KMP - 문자열 매칭 알고리즘

 

KMP 를 통해 풀이한다. 전체 문자열에서 공통되는 접두사와 접미사 부분을 찾고, 그 접두사와 접미사가 문자열 중간에도 등장하는 지를 확인한다. 다른 접두사와 접미사가 등장할 수도 있기에, i = table[i-1] 을 적용시켜 가장 긴 카멜레온 부분 문자열을 찾는다.

# 13506. 카멜레온 부분 문자열 ( PLATINUM 4 )
import sys
input = sys.stdin.readline

string = list(input().rstrip())

# KMP table
table = [0 for _ in range(len(string))]
i = 0
for j in range(1, len(string)):
  while i > 0 and string[i] != string[j]:
    i = table[i-1]
  if string[i] == string[j]:
    i += 1
    table[j] = i

# KMP
now = string[:table[-1]]

while len(now) > 0:
  res = []
  
  i = 0
  for j in range(len(string)):
    while i > 0 and now[i] != string[j]:
      i = table[i-1]
    if now[i] == string[j]:
      i += 1
      if i == len(now):
        res.append(j - i + 1)
        i = table[i-1]
  #print(res, now)
  if len(res) >= 3 and res[0] == 0 and res[-1] == len(string) - len(now):
    break
  else:
    now = string[:table[len(now)-1]]

if len(now) == 0: print(-1)
else: print(''.join(map(str, now)))