[BOJ] 11585 : 속타는 저녁 메뉴

문제 : https://www.acmicpc.net/problem/11585

---

문자열 KMP

 우리는 주어지는 입력 A, B에서 B를 원형으로 회전시켜가며 A가 있는지 없는지 탐색할 수 있어야된다.

따라서, 문자열 검색인 KMP 알고리즘을 생각해야되고 B를 원형으로 회전시켜가며 생각하는 부분은 B 에다가 B를 한 번 더 붙여주면 쉽게 해결이 된다.

 

예시) 

I W A N T M E A T 

E A T I W A N T M 를

E A T I W A N T M E A T I W A N T M 에서 I W A N T M E A T 을 찾는 문제로 바꿔서 바라보면 쉽게 해결할 수 있다.

#include<iostream>
#include<vector>

using namespace std;

int N;
char input1[1000001], input2[2000001];

vector<int> getPartialMatch() {
	vector<int> pi(N, 0);
	int begin = 1, matched = 0;
	while (begin + matched < N) {
		if (input1[begin + matched] == input1[matched]) {
			matched++;
			pi[begin + matched - 1] = matched;
		}
		else {
			if (matched == 0) begin++;
			else {
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}
	return pi;
}

int KMP() {
	int cnt = 0;
	vector<int> pi = getPartialMatch();
	int begin = 0, matched = 0;
	while (begin < N) {
		if (matched < N && input2[begin + matched] == input1[matched]) {
			matched++;
			if (matched == N) cnt++;
		}
		else {
			if (matched == 0) begin++;
			else {
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}
	return cnt;
}
int gcd(int A, int B) {
	while (B) {
		int r = A % B;
		A = B;
		B = r;
	}
	return A;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> input1[i];
	for (int i = 0; i < N; i++)
		cin >> input2[i];
	for (int i = N; i < 2 * N; i++)
		input2[i] = input2[i - N];
	int cnt = KMP();
	int r = gcd(N, cnt);
	cout << cnt / r << '/' << N / r << '\n';
	return 0;
}

---