흙금이네 블로그

아이디어 KMP 알고리즘으로 패턴의 길이를 찾아 나간다. 풀이 i+1은 인덱스 i까지 문자열의 길이를 나타내고, j는 그 문자열에서 접두사와 접미사가 일치하는 부분의 길이를 나타낸다. i+1에서 j를 빼면 패턴의 길이를 알 수 있는데, 이때 문자열 길이 i+1가 패턴의 길이 i+1-j로 나누어 떨어져야 한다. 값이 나누어 떨어지면서 그 몫(패턴의 수)이 1보다 크면 주기문이므로 해당 문자열의 길이와 패턴의 수를 출력한다. def solution(): S = input() N = len(S) lps = [0]*N j = 0 for i in range(1, N): while j > 0 and S[i] != S[j]: j = lps[j-1] if S[i] == S[j]: j += 1 lps[i] = j a, ..