[백준4354번] 문자열 제곱 / Python3

문제

알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, ab는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, ab="abcdef"이다.

이러한 이어 붙이는 것을 곱셈으로 생각한다면, 음이 아닌 정수의 제곱도 정의할 수 있다.

• a^0 = "" (빈 문자열)
• a^(n+1) = a*(a^n)

문자열 s가 주어졌을 때, 어떤 문자열 a에 대해서 s=a^n을 만족하는 가장 큰 n을 찾는 프로그램을 작성하시오.

입력

입력은 10개 이하의 테스트 케이스로 이루어져 있다. 각각의 테스트 케이스는 s를 포함한 한 줄로 이루어져 있다. s의 길이는 적어도 1이며, 백만글자를 넘지 않는다. 마지막 테스트 케이스의 다음 줄은 마침표이다.

출력

각각의 테스트 케이스에 대해, s=a^n을 만족하는 가장 큰 n을 찾은 뒤 출력한다.

예제 입력 1

abcd
aaaa
ababab
.

예제 출력 1

1
4
3

나의 풀이

이 문제는 KMP 알고리즘에서 다룬 접두사, 접미사의 최대 개수를 구하는 함수를 이용한다. 알고보니 이 함수의 이름이 failure function이라고 한다. 이 함수를 통해 결과값으로 나온 배열을 table이라고 하고, 입력받은 문자열을 string이라고 한다면 이 문제를 푸는 공식(?)은 다음과 같다.

len(string) // (len(string) - table[-1])

즉, 문자열의 길이 // (문자열의 길이 - failure function의 마지막 값)이다.

예를들어, ababab가 있다면 failure function을 거쳐 나온 배열은 다음과 같다,

a b a b a b
0 0 1 2 3 4

여기서 공식에 대입해보면 6 // (6 - 4) = 3이다. ab가 3번 반복되므로 정답과 같다. 이것의 원리는 문자열의 길이에서 4를 빼면 2인데 2는 곧 ab의 길이이므로 즉, 반복되는 가장 짧은 부분 문자열의 길이와 같다는 것이다.

그러나 여기서는 예외가 존재한다. 만약, abababa라면 결과값이 어떻게 될까?

a b a b a b a
0 0 1 2 3 4 5

abababa의 failure function의 결과값은 위와 같다. 공식을 적용해보자. 7 // (7 - 5) = 3이다. 그러나 이 문자열의 경우 마지막 a가 가장 짧은 부분 문자열인 ab와 다르기때문에 정답은 1이 나와야한다. 이러한 경우를 잘 살펴보면 문자열의 길이가 홀수인 경우에 해당한다. 따라서 해당 예외를 잡아내기 위해서는 len(string) % (len(string) - table[-1]) != 0을 확인해주면 된다. 즉, 나눈 나머지가 0인가를 판단하여 0이 아니라면 1을 반환해준다면 이 문제는 해결할 수 있다.

코드

# 4354번 문자열 제곱


def failure(p):
    tmp = [0] * len(p)

    j = 0
    for i in range(1, len(p)):
        while j > 0 and p[i] != p[j]:
            j = tmp[j-1]

        if p[i] == p[j]:
            j += 1
            tmp[i] = j

    return tmp


while True:
    string = input()

    if string == '.':
        break

    table = failure(string)

    if len(string) % (len(string) - table[-1]) != 0:    # 나머지 확인
        print(1)
    else:
        print(len(string) // (len(string) - table[-1]))