문제

문자열 s가 있을 때, f(s)는 s를 무한번 붙인 문자열로 정의한다. 예를 들어, s = "abc" 인 경우에 f(s) = "abcabcabcabc..."가 된다.

다른 문자열 s와 t가 있을 때, f(s)와 f(t)가 같은 문자열인 경우가 있다. 예를 들어서, s = "abc", t = "abcabc"인 경우에 f(s)와 f(t)는 같은 문자열을 만든다.

s와 t가 주어졌을 때, f(s)와 f(t)가 같은 문자열을 만드는지 아닌지 구하는 프로그램을 작성하시오.

풀이

1. 두 문자열 길이의 최소 공배수를 구함
2. 두 문자열 길이의 최고 공배수 만큼 반복
3. 비교값 출력

코드

#include <stdio.h>
#include <string.h>

int lcm(int a, int b) {
    int max = a > b ? a : b;
    int lcm = max;
    while (lcm % a != 0 || lcm % b != 0) {
        lcm += max;
    }
    return lcm;
}

int main() {
    char s[51], t[51];
    scanf("%s", s);
    scanf("%s", t);
    
    int len_s = strlen(s);
    int len_t = strlen(t);
    
    int l = lcm(len_s, len_t);
    
    char repeated_s[2501] = {0};
    char repeated_t[2501] = {0};
    
    for (int i = 0; i < l / len_s; i++) {
        strcat(repeated_s, s);
    }
    for (int i = 0; i < l / len_t; i++) {
        strcat(repeated_t, t);
    }

    if (strcmp(repeated_s, repeated_t) == 0) {
        printf("1\\n");
    } else {
        printf("0\\n");
    }
    
    return 0;
}