문자열을 한번 더 붙이고 kmp로 고기를 먹을 수 있게 해주는 문자열을 찾으면 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include <stdio.h> #define mv 1000002 char s[mv * 2], p[mv]; int n, f[mv], ans; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf(" %c", &s[i]); s[n + i] = s[i]; } for (int i = 0; i < n; i++) scanf(" %c", &p[i]); for (int i = 1, j = 0; i < n; i++) { while (j && p[i] != p[j]) j = f[j - 1]; if (p[i] == p[j]) f[i] = ++j; } for (int i = 1, j = 0; i < 2 * n; i++) { while (j && s[i] != p[j]) j = f[j - 1]; if (s[i] == p[j]) { if (j == n - 1) { ans++; j = f[j]; } else j++; } } if (n%ans == 0) n /= ans, ans = 1; printf("%d/%d", ans, n); return 0; } | cs |
'BOJ' 카테고리의 다른 글
14617 제 3회 IUPC (0) | 2018.03.09 |
---|---|
10573 증가하는 수 (0) | 2018.02.18 |
4354 문자열 제곱 (0) | 2018.02.18 |
1305 광고 (0) | 2018.02.18 |
1786 찾기 (0) | 2018.02.18 |