백준 1498 - 주기문

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

 

문제

어떤 문자열 X를 n번 연달아 쓴 것을 (X)^n으로 나타내기로 하자. 예를 들어 (ab)^3는 ababab를 의미한다. 어떤 문자열 Y가 (X)^n 꼴로 표현될 수 있다면, 그리고 n이 1이 아니라면 Y를 주기문 이라고 한다. 예를 들어 ab는 주기문이 아니지만, abab는 (ab)^2으로 표현할 수 있으므로 주기문이 된다.

문자열 S(2 ≤ S의 길이 ≤ 1,000,000)가 주어졌을 때, S의 앞에서부터 i개의 문자가 주기문의 형태가 되는 경우를 찾으려 한다. 가능한 경우가 여럿일 경우에는 n이 최대가 되는 경우를 구하려고 한다. S는 알파벳 소문자로만 이루어져 있다.

문자열 S가 주어졌을 때, 가능한 i, n 쌍을 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S가 주어진다.

출력

i가 증가하는 순서대로, i, n 값을 한 줄에 하나씩 출력한다.

풀이 과정

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 실패 함수를 이용해 접두사와 접미사의 최대 일치 부분을 구해서 풀이하는 문제이다.

 

문자열이 주기문이라면, 특정 문장이 반복해서 이어져 있기 때문에, 접두사와 접미사의 최대 일치 부분 길이가 동일하거나 (abcdabcd -> 최대 일치 부분 4 -> 주기 4), 접두사와 접미사의 최대 일치 부분 길이가 문자열의 길이 절반보다 커서, 문자열의 길이 - 접두사와 접미사의 최대 일치 부분 길이 가 주기가 될 수 있다. (abcabcabc -> 최대 일치 부분 6 -> 주기 3)

 

문자열의 길이가 1일 때부터 순회하며, KMP 실패 함수를 통해 구해놓은 접두사와 접미사의 최대 일치 부분 길이 테이블을 통해 접두사와 접미사가 주기를 이루는지를 확인한다.

# 1498. 주기문 ( PLATINUM 4 )
import sys
input = sys.stdin.readline

s = input().rstrip()

# 주기문이라면 경게가 같거나 겹칠 것
# abcdabcd -> 4 ( 8 - 4 = 4 )
# abababab -> 6 ( 8 - 6 = 2 )
# abcabcabc -> 6 ( 9 - 6 = 3 )

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

result = []

for i in range(1, len(s)):
  if (i+1) % ((i + 1) - table[i]) == 0:
    now = (i+1) // ((i + 1) - table[i])
    if table[i] >= ((i+1)//2):
      result.append([i+1, now])

for l in result:
  print(' '.join(map(str, l)))