백준 : 10266

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

10266번: 시계 사진들

 

문제의 input으로는 어느 바늘을 기준으로 시계바늘이 있는 위치를 간격 0 ~ 360000 으로 보여준다.

 

이것은 0과 1을 가지는 문자열로 나타낸다면 문자열 길이 360,000인 00011001011110 비트형태의 문자열을 만들수가있다.

 

이상태에서 기존 비교해야할 문자열을 길이를 두배로하고 KMP알고리즘을 이용해서 origin 에 pattern이 존재여부를 확인하면 같은 시간을 가리키는가? 를 확인 할 수 있다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B10266 {
	static int N;
	static int[] strIndex = new int[360000];
	static int[] patternIndex = new int[360000];

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

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

		// strIndex Input
		st = new StringTokenizer(br.readLine());
		while (st.hasMoreTokens()) {
			strIndex[Integer.parseInt(st.nextToken())] = 1;
		}

		st = new StringTokenizer(br.readLine());
		while (st.hasMoreTokens()) {
			patternIndex[Integer.parseInt(st.nextToken())] = 1;
		}

		StringBuilder sb = new StringBuilder();

		for (int i = 0; i < 360000; i++)
			sb.append(strIndex[i]);

		String str = sb.append(sb).toString();
		sb = new StringBuilder();
		for (int i = 0; i < 360000; i++)
			sb.append(patternIndex[i]);

		String pattern = sb.toString();

		if (KMP(str, pattern) == 1)
			System.out.println("possible");
		else
			System.out.println("impossible");

	}

	static int[] getPi(String Pattern) {
		int[] pi = new int[Pattern.length()];

		int j = 0;

		for (int i = 1; i < Pattern.length(); i++) {

			while (j > 0 && Pattern.charAt(i) != Pattern.charAt(j)) {
				j = pi[j - 1];
			}
			if (Pattern.charAt(i) == Pattern.charAt(j)) {
				pi[i] = ++j;
			}
		}
		return pi;
	}

	static int KMP(String Origin, String Pattern) {

		int j = 0;
		int[] pi = getPi(Pattern);
		for (int i = 0; i < Origin.length(); i++) {

			while (j > 0 && Origin.charAt(i) != Pattern.charAt(j)) {
				j = pi[j - 1];
			}

			if (Origin.charAt(i) == Pattern.charAt(j)) {
				if (j == Pattern.length() - 1) {
					return 1;
				} else {
					++j;
				}
			}

		}

		return 0;
	}
}