최소 공통 약수
면접 대비시간 제한2초메모리 제한512 MB
두 짧은 문자열이 주어질 때, 각각을 정수 번 반복해 만들 수 있는 가장 짧은 공통 문자열을 찾고, 없으면 없다고 출력한다.
문제
문자열 의 약수란, 정수 번 반복하면 를 얻을 수 있는 문자열 를 말한다. 예를 들어 문자열 "aaaa"의 약수는 "a", "aa", "aaaa"이고, 문자열 "ababab"의 약수는 "ab"와 "ababab"이다.
두 문자열 와 가 주어진다. 의 약수이면서 동시에 의 약수인 문자열 중 가장 짧은 것을 구하거나, 그러한 문자열이 없음을 판별하라.
입력
첫째 줄에 문자열 , 둘째 줄에 문자열 가 주어진다. 각 문자열의 길이는 1 이상 50 이하이고, 알파벳 소문자로만 이루어져 있다.
출력
문자열 와 의 최소 공통 약수를 출력한다. 최소 공통 약수가 존재하지 않으면 "No solution"을 출력한다.