풀이
원순열을 구현하려면 귀찮으니까 똑같은 문자열을 두 번 이어붙여주자
그리고 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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이