Concatenação de Strings

시간 제한0.5초메모리 제한1024 MB

요약

두 문자열 r과 s가 주어질 때 r을 m번, s를 n번 이어 붙인 것이 서로 같아지는 최소의 양의 정수 m, n을 구하고, 없으면 NAO를 출력한다.

난이도: 보통10점 중 5점
유형: 문자열, 정수론, 문자열 매칭
정답자: 아직 제출이 없습니다

문제

Seja s uma string. Denotamos por sn a concatenação de n cópias de s. Por exemplo, se s = “eri” e n = 3, temos s3 = “erierieri”.

Dadas strings r e s, sua tarefa é determinar se existem inteiros m e n tais que rm = sn.

입력

Cada linha da entrada conterá duas strings, separadas por um espaço, compostas apenas por letras minúsculas. Cada uma das strings terá pelo menos 1 e no máximo 1.000.000 caracteres. A última linha da entrada será composta por duas strings “#’ separadas por espaço. Esta linha não deve ser processada.

출력

Para cada linha da entrada, você deve gerar uma linha de saída contendo os menores inteiros m e n separados por espaço caso tais inteiros existam, e “NAO”, em caso contrário.

예제1

예제 1

입력

aa aaa
abra cadabra
abcabcabcabcabcabc abcabcabcabc
rai mano
# #

예상 출력

3 2
NAO
2 3
NAO