[백준] 12871

무한 문자열

문제

문자열 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)가 같은 문자열을 만드는지 아닌지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 s, 둘째 줄에 t가 주어진다. 두 문자열 s와 t의 길이는 50보다 작거나 같은 자연수이고, 알파벳 소문자로만 이루어져 있다.

출력

첫째 줄에 f(s)와 f(t)가 같으면 1을, 다르면 0을 출력한다.

풀이

#include <iostream>
#include <string>

int comp(std::string min, std::string max, int minlen, int maxlen, int lcm) {
    int minrepeat = lcm / minlen;
    int maxrepeat = lcm / maxlen;
    std::string mintemp = "";
    std::string maxtemp = "";

    while (minrepeat-- > 0)
        mintemp += min;
    while (maxrepeat-- > 0)
        maxtemp += max;

    return mintemp == maxtemp;
}

int lcm(int a, int b) {
    int c;
    int aTemp = a, bTemp = b;

    while (b != 0) {
        c = a % b;
        a = b;
        b = c;
    }
    return aTemp * bTemp / a;
}

int main(void) {
    std::string s, t;
    int slen, tlen, lcmlen;

    std::cin >> s >> t;
    slen = s.length();
    tlen = t.length();
    lcmlen = lcm(slen, tlen);
    if (slen > tlen)
        std::cout << comp(t, s, tlen, slen, lcmlen);
    else
        std::cout << comp(s, t, slen, tlen, lcmlen);
}

반성회

처음엔 길이가 짧은 문자열을 반복해서 길이가 긴 문자열을 만들 수 있으면 1인 줄 알았는데

그렇게 하면 aa, aaa 같은 반례에서 걸린다 (짧은 문자열로 긴 문자열을 만들 순 없지만 무한히 반복하면 두개가 같아짐)

그래서 최소공배수를 구해서 그 길이가 되게끔 반복시켜 비교하는 방식으로 풀었다