[17609] 회문

https://www.acmicpc.net/problem/17609

17609번: 회문

<문제>

회문에대한 판별은 여기를 참고하자. [1259] 팰린드롬수 :: Dizlet-Algorithm (tistory.com)

[1259] 팰린드롬수

유사회문에 대한 판별이 이 문제의 핵심 요구사항이다. 유사회문은 아래와 같은 방식으로 판별할 수 있다.

 

1) 회문에 대한 판별을 진행한다. 도중, s[i]!=s[j]이면 아래의 3가지로 나뉜다.

1-1 : s[i+1] == s[j]이면, s[i]를 제외하고 회문인지를 판별한다.

1-2 :  s[i] == [j -1]이면, s[j]를 제외하고 회문인지를 판별한다.

1-3 : s[i + 1] != s[j] && s[i] != s[j - 1] 이면, 문자를 한개 지워도 회문이 아니다. 조기에 false를 리턴한다.

 

회문도 아니고, 유사회문도 아니라면 2를 출력하면 된다.

<소스코드>

#include<stdio.h>
#include<string.h>
char s[100001];
bool f(void) {
    int i, j;
    for (i = 0, j = strlen(s) - 1; i < j; i++, j--)
        if (s[i] != s[j]) return false;
    return true;
}
bool g(void) {
    int i, j, x, y, start, end, res_1, res_2, key;
    key = false;
    for (i = 0, j = strlen(s) - 1; i < j; i++, j--) {
        if (s[i] == s[j])continue;//회문을 만족
        if (s[i + 1] != s[j] && s[i] != s[j - 1])return false;//문자를 1개 지워도 회문 불만족
 
        if (s[i + 1] == s[j]) {//s[i]를 제거후 회문인 경우, res_1 = true
            res_1 = true;
            start = i + 1,end=j;
            for (; start < end; start++, end--) {
                if (s[start] != s[end]) {
                    res_1 = false;
                    break;
                }
            }
            if (res_1 == true)return true;
        }
        if (s[i] == s[j - 1]) {//s[j]를 제거후 회문인 경우, res_2 = true
            res_2 = true;
            start = i, end = j - 1;
            for (; start < end; start++, end--) {
                if (s[start] != s[end]) {
                    res_2 = false;
                    break;
                }
            }
            if (res_2 == true)return true;
        }
        return false;
    }
}
int main(void) {
    int t, i;
    scanf("%d", &t);
    for (i = 0; i < t; i++) {
        scanf("%s", s);
        if (f() == true)//회문
            printf("0\n");
        else if (g() == true)//유사회문
            printf("1\n");
        else
            printf("2\n");
    }
    return 0;
}