코드 복사/붙여넣기 하는 당신이 아름답습니다.

11585 : 속타는 저녁 메뉴

풀이

원순열을 구현하려면 귀찮으니까 똑같은 문자열을 두 번 이어붙여주자

그리고 kmp를 돌려서 substring으로 등장하는 횟수를 구해주자

코드

#include <cstdio>

const int n_ = 1e6 + 5;

int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }

int n, i, j, cnt, fail[n_];
char a[n_], b[n_ * 2];

int main() {
	scanf("%d", &n);
	for (i = 0; i < n; i++) scanf(" %c", &a[i]);
	for (i = 0; i < n; i++) scanf(" %c", &b[i]), b[i + n] = b[i];

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

	for (i = 0, j = 0; i < n * 2 - 1; i++) {
		while (j && b[i] != a[j]) j = fail[j - 1];
		if (b[i] == a[j]) (j == n - 1) ? (j = fail[j], cnt++) : j++;
	}

	int d = gcd(cnt, n);
	printf("%d/%d\n", cnt / d, n / d);

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-03-30 15:36

Read more posts by this author