(BOJ4354 문자열 제곱

• tags : (algorithm

  No matching post could be found

  - (KMP
• 문제 링크 : https://www.acmicpc.net/problem/4354
• 풀이 링크
  • Python

• 부분 문자열 중에서 부분 문자열의 반복만으로 원래 문자열을 만들수 있는지, 만들 수 있다면 부분 문자열의 최소 크기를 찾아야 하는 문제
• 문제에서는 문자열 제곱이라 표현했지만, 실제로는 문자열을 뒤에 이어 붙이는 연산을 원한다.
• solved.ac 난이도, KMP가 표시되어 있지만, Python일반적인 문자열 연산으로도 해결할 수 있다.

while True:
    seq = input().strip()
    if seq == ".":
        break
    len_seq = len(seq)
    idx = 0
    check = [0] * len_seq
    for i in range(1, len_seq):
        while idx and seq[idx] != seq[i]:
            idx = check[idx - 1]
        if seq[idx] == seq[i]:
            idx += 1
            check[i] = idx
    max_len = len_seq - check[-1]
    if len_seq % max_len:
        print(1)
    else:
        print(len_seq // max_len)

• KMP를 활용한 풀이
• 문자열 길이의 패턴 확인용 리스트와 패턴을 확인하기 위한 인덱스를 선언하고,
• 문자열을 처음부터 확인하며 접두어와 접미어가 같은 위치를 표시한다.
• 마지막 출력은 가능한 최대 길이를 구한 뒤, 정답을 출력한다.

while True:
    seq = input().strip()
    if seq == ".":
        break
    len_seq = len(seq)
    for i in range(1, len_seq + 1):
        if len_seq % i:
            continue
        target = seq[:i]
        if target * (len_seq // i) == seq:
            print(len_seq // i)
            break

• 앞에서부터 문자열 길이를 하나씩 늘려가며 해당 문자열의 반복만으로 문자열을 만들어 낼 수 있는지 확인한다.