[BOJ] 11585 속타는 저녁 메뉴

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

 

문제 풀이:

첫 번째 문자열을 a라고 하고, 찾아야 할 문자열을 b라고 하자.

a는 원형이기 때문에

a가 [abcd]라면 [abcdabc]로 만들어 준다.

 

그리고 kmp로 고기 먹을 수 있는 경우의 수를 구하고,

gcd를 구해 나눠준 후 출력한다.

 

하지만 이렇게 하면 a 배열 크기를 두 배로 사용한다. 메모리를 많이 사용하고 싶지 않다면 [소스 코드 2] 풀이처럼 풀 수도 있다.

 

* gcd 함수에서, else문에서 return으로 안하고 바로 gcd 호출하도록 했더니 런타임 에러가 났다 ㅎㅎ 댕청-

 

 

 

소스 코드 1:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>

using namespace std;

char a[2000003],b[1000002];
int n,fail[1000002],cnt;

int gcd(int val1, int val2) {
	if (val2 == 0) return val1;
	else return gcd(val2, val1%val2);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) cin >> b[i];

	int len = n;
	for (int i = 0; i < n - 1; i++) a[len++]=a[i];

	for (int i = 1, j = 0; i < n; i++) {
		while (j > 0 && b[i] != b[j]) j = fail[j-1];
		if (b[i] == b[j]) fail[i] = ++j;
	}

	for (int i = 0, j = 0; i < len; i++) {
		while (j > 0 &&  a[i] != b[j]) {
			j = fail[j - 1];
		}

		if (a[i] == b[j]) {
			if (j == n - 1) {
				cnt++;
				j = fail[j];
			}
			else j++;
		}
	}
	int gcdV = gcd(n, cnt);

	cout << cnt/gcdV<<"/"<<n/gcdV<< "\n";
	
	return 0;
}

 

소스 코드 2:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>

using namespace std;

char a[1000002],b[1000002];
int n,fail[1000002],cnt;

int gcd(int val1, int val2) {
	if (val2 == 0) return val1;
	else return gcd(val2, val1%val2);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) cin >> b[i];


	for (int i = 1, j = 0; i < n; i++) {
		while (j > 0 && b[i] != b[j]) j = fail[j-1];
		if (b[i] == b[j]) fail[i] = ++j;
	}
	int len = n * 2 - 1;
	for (int i = 0, j = 0; i < len; i++) {
		int cur = i % n;
		while (j > 0 &&  a[cur] != b[j]) {
			j = fail[j - 1];
		}

		if (a[cur] == b[j]) {
			if (j == n - 1) {
				cnt++;
				j = fail[j];
			}
			else j++;
		}
	}
	int gcdV = gcd(n, cnt);

	cout << cnt/gcdV<<"/"<<n/gcdV<< "\n";
	
	return 0;
}