만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

우유 짜기 격자

면접 대비

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

요약
R행 C열 격자가 주어졌을 때, 가장자리에서 잘려도 반복하면 격자 전체를 만들 수 있는 가장 작은 넓이의 직사각형을 구합니다.
난이도

보통10점 중 5점

유형
문자열, 문자열 매칭, 완전 탐색
정답자
아직 제출이 없습니다

문제

매일 아침 젖을 짤 때, 농부 존의 소들은 R행 C열의 직사각형 격자를 이룬다. 여기서 1≤R≤10,0001 \le R \le 10{,}000, 1≤C≤751 \le C \le 75이다. 존은 소의 사료 섭취 행동에 관한 책을 쓰고 있다. 각 소에는 품종을 나타내는 대문자 알파벳이 붙어 있다. 젖을 짜는 동안 소들이 이루는 2차원 무늬는 더 작은 직사각형 무늬가 반복된 것처럼 보일 때가 있다.

격자 전체를 반복해서 채워 만들 수 있는, 넓이가 가장 작은 직사각형 단위를 찾아라. 단위의 가로와 세로는 격자의 가로와 세로를 나누어떨어뜨릴 필요가 없다.

입력

첫 줄에 공백으로 구분된 정수 R과 C가 주어진다. 이어지는 R줄에는 각각 C개의 대문자가 공백이나 다른 문자 없이 붙어서 주어진다. i+1i+1번째 줄은 격자의 ii번째 행이다.

출력

격자를 만들 수 있는 가장 작은 단위의 넓이를 한 줄에 출력한다.

힌트

격자 전체는 'AB' 무늬를 반복해서 만들 수 있다.

예제1

  1. 예제 1

    입력
    2 5
    ABABA
    ABABA
    
    예상 출력
    2