11585 속타는 저녁 메뉴

문자열을 한번 더 붙이고 kmp로 고기를 먹을 수 있게 해주는 문자열을 찾으면 된다.

 

#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;
}