회문(palindrome)에 대해 알아보자
회문
회문 SWEA 회문2 SWEA
회문이란 앞으로 읽어도 뒤로 읽어도 같은 단어이다. 회문1 같은 경우에는 8x8 단어판와 길이가 주어지면 그 단어판에서 길이만큼의 회문 갯수를 세면 된다.
회문1
1string temp;
2for (int i=n; i<n+len; i++) {
3 temp += v[i][m];
4}
5string temp2 = temp;
6reverse(temp.begin(),temp.end());
7if(temp == temp2)
8 ans++;
와 같이 뒤집은 문자와 문자가 같으면 회문으로 처리했다.
회문2
회문2의 경우에는 회문1에서 단어판을 100x100으로 키우고 최대의 길이의 회문을 찾으면 된다.
1int x(int len, int pos_y, int pos_x) {
2 for (int i=0; i<len/2; i++) {
3 if(v[pos_y][pos_x + i] != v[pos_y][pos_x + len - 1 - i])
4 return 0;
5 }
6 return len;
7}
8int y(int len, int pos_y, int pos_x) {
9 for (int i=0; i<len/2; i++) {
10 if(v[pos_y + i][pos_x] != v[pos_y + len - 1 - i][pos_x])
11 return 0;
12 }
13 return len;
14}
15
16for (int k=1; k<100; k++) {
17 for (int i=0; i<=100-k; i++) {
18 for (int j=0; j<100; j++) {
19 temp = y(k,i,j);
20 len = max(len,temp);
21 }
22 }
23 for (int i=0; i<100; i++) {
24 for (int j=0; j<=100-k; j++) {
25 temp = x(k,i,j);
26 len = max(len,temp);
27 }
28 }
29}
k가 길이, i가 열, j가 행으로 잡고 길이가 k일때 (i,j)에서 시작하는 회문을 찾고 있으면 길이를 반환해서 len값과 비교해서 큰 값을 len에 넣는다.