Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

34. 문자열 알고리즘 1

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

4. 시계 사진들

10266번

문자열 찾기 알고리즘을 응용하는 문제

이번 문제는 두 사진에 대한 묘사가 주어질 때, 두 사진의 시계가 같은 시각을 나타내는지 결정하는 문제이다.

clock2를 이용해 pi를 구하고, clock1을 이어 붙인 배열에서 clock2를 찾는다.

KMP 알고리즘을 활용하여 구현할 수 있다. Pi 배열을 이용한다.

Java / Python

• Java

import java.io.*;
import java.util.*;

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));

		int N = Integer.parseInt(br.readLine());

		int[] clock1 = new int[720000];
		int[] clock2 = new int[360000];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			int t = Integer.parseInt(st.nextToken());
			clock1[t] = 1;
			clock1[t + 360000] = 1;
		}

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			clock2[Integer.parseInt(st.nextToken())] = 1;
		}

		bw.write(KMP(clock1, clock2));

		bw.flush();
		bw.close();
		br.close();
	}

	public static String KMP(int[] t, int[] p) {
		int pi[] = getPi(p);
		int j = 0;
		for (int i = 0; i < t.length; i++) {
			while (j > 0 && t[i] != p[j]) {
				j = pi[j - 1];
			}
			if (t[i] == p[j]) {
				if (j + 1 == p.length) {
					return "possible";
				} else {
					++j;
				}
			}
		}
		return "impossible";
	}

	public static int[] getPi(int[] pattern) {
		int[] pi = new int[pattern.length];
		int j = 0;
		for (int i = 1; i < pattern.length; i++) {
			while (j > 0 && pattern[i] != pattern[j]) {
				j = pi[j - 1];
			}
			if (pattern[i] == pattern[j])
				pi[i] = ++j;
		}
		return pi;
	}
}

• Python

import sys
input = sys.stdin.readline

def getPi(p):
    pi = [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


def KMP(c1, c2):
    pi = getPi(c2)

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

        if c1[i] == c2[j]:
            if j == len(c2) - 1:
                return True
            else:
                j += 1
    return False

N = input()
clock1 = [0] * 360000
clock2 = [0] * 360000


for i in map(int, input().split()):
    clock1[i] = 1

clock1 += clock1

for i in map(int, input().split()):
    clock2[i] = 1

if KMP(clock1, clock2):
    print("possible")
else:
    print("impossible")