부분 직사각형
시간 제한2초메모리 제한128 MB
N x M 표를 2N x 2M으로 복사한 뒤 모든 부분 사각형에서 각 알파벳이 총 몇 번 나타나는지 구합니다.
문제
민식이는 크기가 N x M이고 대문자 알파벳으로 채워진 직사각형 표를 가지고 있다. 이 표를 가로와 세로로 한 번씩 복사해, 원래 표 네 개가 2 x 2로 붙은 크기 2N x 2M의 큰 표를 만든다. 그다음 이 큰 표에서 만들 수 있는 모든 부분 직사각형을 하나씩 생각한다.
다음과 같은 크기 1 x 2 표를 보자.
OK
이 표를 2 x 2개의 복사본으로 붙이면 큰 표는 다음과 같다.
OKOK
OKOK
이 큰 표에는 부분 직사각형이 30개 있다. 아래에서 .은 구분을 위해 적은 문자이다.
OKOK .... OKOK OKO. .... OKO. .KOK .... .KOK OK.. .... OK.. .KO. .... .KO.
OKOK OKOK .... OKO. OKO. .... .KOK .KOK .... OK.. OK.. .... .KO. .KO. ....
..OK ..OK .... O... .... O... .K.. .... .K.. ..O. .... ..O. ...K .... ...K
..OK .... ..OK O... O... .... .K.. .K.. .... ..O. ..O. .... ...K ...K ....
큰 표의 모든 부분 직사각형을 통틀어 각 대문자 알파벳이 총 몇 번 등장하는지 구하시오. 위의 경우 K는 40번, O는 40번 등장한다.
입력
첫째 줄에 두 정수 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표의 각 행을 나타내는 문자열이 주어진다. 모든 문자는 대문자 알파벳이다.
출력
총 26줄을 출력한다. 첫째 줄에는 A의 총 등장 횟수, 둘째 줄에는 B의 총 등장 횟수, 이와 같은 방식으로 Z까지의 총 등장 횟수를 출력한다.
제한
- 1 <= N, M <= 50