백준 3356 - 라디오 전송

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

 

문제

라디오 방송국은 메시지를 여러 청취자에게 전송한다. 모든 청취자가 메시지를 확실히 받게 하기 위해서 메시지를 계속해서 반복 전송한다.

한 청취자가 받은 메시지가 주어진다. 항상 청취자가 받은 메시지의 길이는 방송국에서 보낸 메시지의 길이보다 크거나 같다. 이때, 라디오 방송국에서 보낸 메시지를 구하는 프로그램을 작성하시오.

즉, 입력으로 S가 주어졌을 때, S가 S' + S' + ... + S'의 부분 문자열이 되는 가장 짧은 부분수열 S'를 구하는 프로그램을 작성하시오. 

입력

첫째 줄에 S의 길이 L이 주어진다. 둘째 줄에는 길이가 L인 S가 주어진다. 메시지는 알파벳 소문자로만 이루어져 있다. (1 ≤ L ≤ 1,000,000)

출력

첫째 줄에 S'의 길이 L'을 출력한다.

풀이 과정

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 실패 함수를 이용해 풀이한다. 전체 문자열의 길이에서 공통되는 접두사 및 접미사 부분 길이를 제외하면 방송국에서 보낸 메시지이고, 공통되는 접두사 및 접미사 부분이 전체라면 그 전체 길이가 방송국에서 보낸 메시지이다.

# 3356. 라디오 전송 ( PLATINUM 4 )
import sys
input = sys.stdin.readline

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

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

if table[-1] == 0: print(l)
else: print(l - table[-1])