[BOJ] 무한 문자열 12871번 C++

 

 

문제

문자열 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을 출력한다.

 

 

접근 방식

 

예시는 ab, abab 이런 것들이라서  처음에 문제를 풀 때 간과했던 것이 있다.

abcabcabc, abababab 가 각각 s와 t라면 두개의 문자열 모두 가장 최소 문자열을 찾아서 비교해 주어야 한다

즉, 두 문자의 최소 문자열을 찾아 같은지 확인해주면 된다..!

 

코드

 

#include<bits/stdc++.h>
using namespace std;

string sol(const string& str) {
    int n = str.size();

    for(int i=1; i<=n; i++) {
        if(n % i == 0) {
            string unit = str.substr(0,i);
            string tmp = "";

            for(int j=0; j<n/i; j++) tmp += unit;
            if(tmp == str) return unit;

        }
    }
    return str;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    string s,t; cin>>s>>t;

    string min_s = sol(s);
    string min_t = sol(t);

    if(min_s == min_t) cout<<1;
    else cout<<0;
}