백준 3779 - 주기

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

 

문제

아스키 코드가 97이상 126이하인 N개의 문자로 이루어진 문자열 S가 주어진다. 문자열 S의 모든 접두사에 대해, 각각의 접두사가 주기적인 문자열인지 아닌지 알고 싶다. 다시 말해 2 ≤ i ≤ N을 만족하는 각각의 i에 대해, 길이가 i인 문자열 S의 접두사가 어떤 문자열 A에 대해 AK 형태로 표현할 수 있는 가장 큰 K > 1을 알아내려 한다.

AK란 문자열 A가 K번 연속되어있는 문자열을 의미한다. A = "abad"이고, K = 3인 경우 AK = "abadabadabad"이다.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 두 줄로 이루어진다. 테스트 케이스의 첫 번째 줄에는 문자열 S의 길이인 정수 N이 주어진다 (2 ≤ N ≤ 1 000 000). 테스트 케이스의 두 번째 줄에는 문자열 S가 주어진다. 입력의 끝은 0으로 주어진다.

출력

각 테스트 케이스에 대해, "Test case #"과 테스트 케이스의 번호를 한 줄에 출력한다. 그 후, 길이가 i인 접두사의 주기가 K > 1인 경우, 접두사의 길이 i와 주기 K를 공백으로 분리하여 한 줄에 출력한다. 이때, 접두사의 길이가 오름차순이 되도록 출력하여야 한다. 각 테스트 케이스에 대한 답을 출력한 후, 빈 줄을 한 줄 출력하여야 한다.

풀이 과정

https://readytojoin.tistory.com/entry/%EB%B0%B1%EC%A4%80-1498-%EC%A3%BC%EA%B8%B0%EB%AC%B8

백준 1498 - 주기문

1498 문제와 동일하다. KMP 실패 함수를 사용해 풀이한다.

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 - 문자열 매칭 알고리즘

 

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

tc = 1
while True:
  n = int(input().rstrip())
  if n == 0: break
  if tc >= 2: print()
    
  s = list(input().rstrip())
  
  print('Test case #%d'%tc)
  tc += 1

  table = [0 for _ in range(n)]
  i = 0
  for j in range(1, n):
    while i > 0 and s[i] != s[j]:
      i = table[i - 1]

    if s[i] == s[j]:
      i += 1
      table[j] = i
  res = []
  for i in range(1, n):
    if table[i] >= (i + 1) // 2 and (i + 1) % ((i + 1) - table[i]) == 0:
      res.append([i+1, (i + 1) // ((i + 1) - table[i])])
  res.sort(key=lambda x: (x[0] // x[1]))
  for r in res:
    print(' '.join(map(str, r)))