DNPALIN - Double Near Palindromes

no tags 

C-3PO is an expert in pretty much every language. His conversation with R2-D2 are always fun to observe un that R2-D2 speaks in Droid, C-3PO speak in English, and they understand each other perfectly! Anyway, humans and droids both enjoy playing word games. A palindrome is a word or sequence of one or more letters that reads the same forwards and backwards. A near palindrome is a word or sequence that can be changed to or kept a palindrome by changing exactly one letter to a different letter. For example. BAT is a near palindrome, since changing the T to a B woluld make the word a palindrome: BAB. PEEP is not a near palindrome: although PEEP is palindrome, changing any letter would remove its palindrome status. A double near palindrome is a word or sequence that consist of two near palindromes concatenated together. For example, BATMAN is a double near palindrome, since BAT and MAN are both near palindromes. Given a list of words, you are to determine wich words are double near palindromes and wich are not.

Input

The input consists of one or more words. All words (except the last) will be inclusively between 1 and 25 letters long and will consist of entirely of capital letters. The last word will be *END* and is not be processed; it simply indicates the end of the input. There may be any number of spaces and characters before, after, and between words.

Output

The output cases are to appear in the same order in wich they appear in the input. For each input case, you are to print either w is a double near palindrome. or w is not a double near palindrome. wichever is appropriate, where w is the input word. Exactly one should follow each output case (meaning there should be no blank lines in the output).

Example

Input:
BATMAN
CONSTANTINOPLE
*END*

Output:
BATMAN is a double near palindrome.
CONSTANTINOPLE is not a double near palindrome.


hide comments
Projjal Kundu: 2016-01-25 07:59:10

why is PEEP not a double near palindrome??
PEEP can be broken into PE and EP, in each of them changing one letter would make them palindrome

The_ROCK: 2013-12-25 07:01:53

" There may be any number of spaces and characters before, after, and between words." here 'characters' means only spaces and newlines and not stray symbols or small letters.

BLANKRK: 2013-08-16 04:14:52

nice :)

npsabari: 2012-07-18 14:01:36

O(N^2) dp problem!

Sai Praneeeth: 2012-05-27 17:02:45

@ Baba Ramdev NO such test cases.
Just treat a word in single line to be a single test case.

.::Manish Kumar::.: 2011-06-12 18:45:44

Can the input be like this too::
BATMANisaassh***CONSTANTIPOLEmm
*END*

and output should be::
BATMAN is a double near palindrome.
CONSTANTINOPLE is not a double near palindrome.

Vladimir Tsibrov: 2011-05-26 05:26:52

"aa" is a double near palindrome!

hendrik: 2010-06-13 13:02:32

Watch out! Weird input! The input can be like
BATMAN CONSTANTINOPLE
*END*
And it should still be the same output as above. Whats the point of that? It doesnt make the actual problem harder.

Last edit: 2010-06-13 13:30:29
Ishan: 2010-04-26 03:44:13

'aa' is it a double near palindrome?

Ankul Garg: 2009-06-25 18:15:50

c = a[1..m]b[1..n] string b comes after string a, hope u got it

Last edit: 2009-06-25 18:16:45

Added by:Daniel Gómez Didier
Date:2008-11-18
Time limit:1.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:2007 U.Nacional - Circuito de Maratones ACIS / REDIS