Bài 14.3. Từ Vang Ngược - Đệ quy Palindrome - [Độ khó: Khá]

Trong một ngôn ngữ cổ đại huyền bí, có những từ được gọi là "Đệ quy Palindrome". Một từ được gọi là Đệ quy Palindrome nếu nó thỏa mãn các điều kiện sau:

1. Bản thân từ đó là một palindrome (đọc xuôi và ngược đều giống nhau).
2. Nếu từ đó có độ dài lớn hơn 2, thì chuỗi con tạo thành từ các ký tự bên trong (bỏ đi ký tự đầu tiên và cuối cùng) cũng phải là một Đệ quy Palindrome.
3. Các từ rỗng hoặc chỉ có một ký tự luôn được coi là Đệ quy Palindrome (trường hợp cơ sở).

Bạn là một nhà khảo cổ học và đã tìm thấy một văn bản cổ. Để hiểu được ý nghĩa của nó, bạn cần xác định xem các từ trong văn bản có phải là Đệ quy Palindrome hay không.

INPUT FORMAT

Một dòng duy nhất chứa chuỗi \(S\) (\(1 \le |S| \le 1000\)), bao gồm các ký tự chữ cái viết thường tiếng Anh.

OUTPUT FORMAT

In ra TRUE nếu \(S\) là một Đệ quy Palindrome, ngược lại in ra FALSE.

Ví dụ 1:

Input:

abacaba

Output:

TRUE

Giải thích:

1. "abacaba" là palindrome.
2. Độ dài lớn hơn 2, xét chuỗi con bên trong là "bacab".
   1. "bacab" là palindrome.
   2. Độ dài lớn hơn 2, xét chuỗi con bên trong là "aca".
      1. "aca" là palindrome.
      2. Độ dài lớn hơn 2, xét chuỗi con bên trong là "c".
         1. "c" là palindrome (trường hợp cơ sở). Vậy, "c" là Đệ quy Palindrome. Do đó "aca" là Đệ quy Palindrome. Do đó "bacab" là Đệ quy Palindrome. Do đó "abacaba" là Đệ quy Palindrome.

Ví dụ 2:

Input:

abca

Output:

FALSE

Giải thích: "abca" không phải là palindrome, vì vậy nó không thể là Đệ quy Palindrome.

Ví dụ 3:

Input:

racecar

Output:

TRUE

Giải thích:

1. "racecar" là palindrome.
2. Xét chuỗi con bên trong là "aceca".
   1. "aceca" là palindrome.
   2. Xét chuỗi con bên trong là "cec".
      1. "cec" là palindrome.
      2. Xét chuỗi con bên trong là "e".
         1. "e" là palindrome (trường hợp cơ sở). Vậy, "e" là Đệ quy Palindrome. Do đó "cec" là Đệ quy Palindrome. Do đó "aceca" là Đệ quy Palindrome. Do đó "racecar" là Đệ quy Palindrome.