Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

34. 문자열 알고리즘 1

KMP 알고리즘과 트라이 자료구조를 다뤄 봅시다.

2. 문자열 제곱

4354번

KMP의 failure function을 활용하는 문제 1

이번 문제는 문자열 s가 주어졌을 때, 어떤 문자열 a에 대해서 s=a^n을 만족하는 가장 큰 n을 찾는 문제이다.

저번 문제 (1786번 찾기) 처럼 KMP 알고리즘을 활용하여 구현할 수 있다. Pi 배열을 이용한다.

Java / Python

• Java

import java.io.*;

public class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String ptn;
		StringBuilder sb = new StringBuilder();
		while(!(ptn = br.readLine()).equals(".")) {
			int max = getMaxPi(ptn);
			sb.append(max).append("\n");
		}
		
		bw.write(sb.toString());
		
		bw.flush();
		bw.close();
		br.close();
	}
	
	// pi배열의 최댓값 구하기 
	static int getMaxPi(String ptn) {
		int j = 0;
		int len = ptn.length();
		int[] pi = new int[len];
		
		for(int i = 1; i < len; i++) {
			while(j > 0 && ptn.charAt(i) != ptn.charAt(j)) {
				j = pi[j - 1];
			}
			if(ptn.charAt(i) == ptn.charAt(j)) {
				pi[i] = ++j;
			}
		}
		return len % (len - pi[len - 1]) != 0 ? 1 : len / (len - pi[len - 1]);
	}
}

• Python

import sys

def getPi(P):
    pi = [0 for _ in range(0, len(P))]
    j = 0
    
    for i in range(1, len(P)):
        while j > 0 and P[i] != P[j]:
            j = pi[j - 1]

        if (P[i] == P[j]):
            j += 1
            pi[i] = j
    return pi[-1]

while True:
    S = sys.stdin.readline().rstrip('\n')
    if len(S) == 1 and S[0] == '.': exit(0)
    len_match = getPi(S)
    if len(S) % (len(S) - len_match) != 0:
        print(1)
    else:
        print(len(S) // (len(S) - len_match))