[문자열 알고리즘 1 단계] 백준 10266번 시계 사진들

문제

상근이는 보통의 시계와는 다른 독특한 시계 사진 두장이 있습니다. 시계는 n개의 동일한 길이와 목적을 가진 시계 바늘들을 가지고 있습니다. 애석하게도 시계의 숫자들은 희미해져 각 시계 바늘들의 위치만 구분 할 수 있습니다.

우리의 상근이는 두 사진의 시계가 같은 시각을 나타낼 수 있는지 궁금해져 각 사진을 서로 다른 각도로 돌려보려고 합니다.

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

입력

첫 줄에는 바늘의 수를 나타내는 정수 n(2 ≤ n ≤ 200 000)이 주어진다.

다음 두줄에는 각각 n개의 정수가 주어지며, 주어지는 정수 ai(0 ≤ ai < 360,000)는 각 사진에서 바늘의 시계 방향 각도를 나타낸다. 이때 바늘의 각도는 특정 순서대로 주어지지는 않는다. 한 줄에는 같은 각도값이 두 번 이상 주어지지 않는다. 즉, 한 시계 안의 모든 각도값은 서로 구분된다.

출력

두 시계 사진이 같은 시각을 나타내고 있다면 "possible"을 아니면 "impossible"을 출력하시오.

 

각도를 배열처럼 표시하고 해당 각도를 찾을 수 있으면 같은 시각이다 .

회전으로 찾는 경우 parent를 이어 붙인 것에서 pattern을 찾으면 된다.

0 0 0 0 0 1 0 0 1 0 0 0  // 6 9 (parent)
0 0 1 0 0 1 0 0 0 0 0 0  // 3 6 (pattern)

경우 찾을 수 있음.

만약 반대의 케이스라면 A에서 B를 못찾음 
따라서 A를 한번 더 이어 붙임.

 

그리고 360000은 포함이 아니다. 인덱스를 포함으로 설정하면 못찾음.

#include <iostream>
#include<vector>
#include <algorithm>
#include<cmath>
#include<queue>
using namespace std;
#define MAX 360000
vector<int> makeTable(string str)
{
	int size = str.size();
	vector<int> table(size, 0);
	int j = 0;
	for (int i = 1; i < size; i++)
	{
		while (j > 0 && str[i] != str[j])
			j = table[j - 1];
		if (str[i] == str[j])
		{
			table[i] = ++j;
		}
	}
	return table;
}

bool KMP(string parent, string pattern)
{
	int parentSize = parent.size();
	int patternSize = pattern.size();
	int j = 0;
	vector<int> table = makeTable(pattern);
	for (int i = 0; i < parentSize; i++)
	{
		while (j > 0 && parent[i] != pattern[j])
			j = table[j - 1];
		if (parent[i] == pattern[j])
		{
			if (j == patternSize - 1)
				return true;
			else
				++j;
		}
	}
	return false;
}

int main() {

	string str1;
	string str2;
	for (int i = 0; i < MAX; i++)
	{
		str1 += '0';
		str2 += '0';
	}
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		str1[num] = '1';
	}
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		str2[num] = '1';
	}

	str1 = str1 + str1;
	if (KMP(str1, str2))
		cout << "possible" << endl;
	else
		cout << "impossible" << endl;

}