[KMP/파이썬] 백준 1097번 : 마법의 문자열 / 플래5

https://www.acmicpc.net/problem/1097

1097번: 마법의 문자열

L개의 문자로 이루어진 문자열 T가 있다. T(i)는 T를 i (0 ≤ i < L)번째 문자부터 시작하게 부터 시작하게 원형 이동한 것이고, 길이는 T의 길이와 같다. 즉, 0 ≤ j < L을 만족하는 모든 j에 대해서, T(i)

www.acmicpc.net

import itertools
n = int(input())
words = []
for _ in range(n):
    words.append(input())
k = int(input())

def kmp(pattern, all_string):
    table = [0 for _ in range(len(pattern))]
    i = 0
    for j in range(1, len(pattern)):
        while i>0 and pattern[i]!=pattern[j]:
            i = table[i-1]

        if pattern[i]==pattern[j]:
            i += 1
            table[j] = i

    # kmp
    count = -1
    i = 0
    for j in range(len(all_string)):
        while i > 0 and pattern[i] != all_string[j]:
            i = table[i-1]

        if pattern[i] == all_string[j]:
            i += 1
            if i == len(pattern):
                count += 1
                i = table[i-1]
    return count == k

answer = 0
permutations = list(itertools.permutations(words, n))
for perm in permutations:
    a = ''.join(list(perm))a
    answer += kmp(a, a+a)
print(answer)

kmp로 풀 수 있다.

만든 문자열 a를 두번 연결시킨뒤 그 연결된 문자열에 대해 kmp로 패턴 등장 횟수를 찾아내면 된다.