[문제]
회문(回文, palindrome)은 어떤 방향으로 읽어도 같은 문자열을 말한다. 예를 들면 “여보 안경 안 보여”, “다 큰 도라지라도 큰다.”, “아들딸이 다 컸다 이 딸들아”은 잘 알려진 회문이다. 이번에는 영문 소문자 문자열만 다룬다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체로는 회문이 아니지만 한 문자를 제거하여 회문으로 만들 수 있으면 이런 문자열을 “유사회문”(quasi palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하면 회문 ‘summus’이 되므로 이것은 유사회문이다. 여러분은 제시된 문자열이 그 자체로 회문인지, 또는 “유사회문”인지, 아니면 그 외 일반 문자열인지를 판단해야 한다.
[입출력]
입력파일 palin.inp의 첫줄에는 정수 $n$ , $3 \leq n \leq 10$이 주어진다. 그 다음 이어지는 $n$개의 각 줄에는 소문자로 구성된 문자열이 하나씩 주어진다. 여러분은 이 문자열이 그 자체로 회문인지, 또는 ‘유사회문’인지, 또는 회문도 유사회문도 아닌지를 판명하여 그 결과를 1, 2, 3으로 구분하여 출력파일 palin.out에 순서대로 출력해야 한다. 입력 문자열의 길이 $l$의 범위는 $3 \leq l \leq 100000$이다.
[예제]
|
palin.inp |
palin.out |
|
4 bookoob summuus ixiyi oooooooooo |
1 // 회문 2 // 유사회문 3 // 회문이 아님 1 // 회문
|
|
7 cocococ cocoococ compupmocc veryvery veryxyrev verymxyrev vemryxmyrev |
1 1 2 3 1 2 3
|
[풀이] $O(LN)$
회문판별은 사람이라면 $O(L)$으로 가능한 걸 알것이다. for loop 돌면서 s[i](이하 앞)와 s[l - i](이하 뒤)가 같은지 판별하면 되니까.
그럼 유사 회문 판별은?
먼저, naive한 방법으로 해보자. 문자 $L$개를 하나하나 제거해서 각각 회문판별을 해보면 된다. 하지만, $O(L^2N)$이므로 다시 생각해볼 필요가 있다.
한 가지 자명한 점은 회문을 판단하다가, 앞 뒤가 다른 문자 쌍이 발견되면, 그 이전까지 비교했던 문자쌍들은 회문의 조건을 만족하므로 '절대'쳐다볼 필요가 없다.
즉, 앞 뒤 쌍을 비교해나가다가, 다른 문자 쌍이 발견 되면 substr에서 유사회문이 되는지를 판별하면 된다. 그런데, 다른 문자쌍 발견 된 순간, 그 문자 쌍 중에 하나를 제거해야 substr이 회문이 될 가능성이 생긴다.
따라서, 회문임을 for loop으로 판단하다가 앞 뒤가 다른 문자쌍이 발견되면 앞 또는 뒤 문자 하나를 제거한 상태로 계속 loop을 이어나가면 된다. 문자 제거는 loop 내부에서 index 1 증가시키거나 감소시키는 형태로 제거했다고 판별이 가능하다.
