output the longest palindrome

[vicestner]

Write a Java program that prints the longest palindrome in an input file to standard output. A palindrome is a string whose reverse is the same as the original. Ignore case, whitespace, and punctuation in the input. If there are more than one palindrome of the maximum length, print the first one. Remove all space and punctuation and convert upper case to lower case in the output. If the input file contains:

Was it a rat I saw?

Your program prints:

% java Palindrome < inputfile
wasitaratisaw

[JosAH]

Write a Java program that prints the longest palindrome in an input file to standard output. A palindrome is a string whose reverse is the same as the original. Ignore case, whitespace, and punctuation in the input. If there are more than one palindrome of the maximum length, print the first one. Remove all space and punctuation and convert upper case to lower case in the output. If the input file contains:

Was it a rat I saw?

Your program prints:

% java Palindrome < inputfile
wasitaratisaw

Should the program print the same if it were feeded;

Foo Was it a rat I saw bar?

kind regards,

Jos

[vicestner]

Should the program print the same if it were feeded;

Foo Was it a rat I saw bar?

kind regards,

Jos

yes, it will still print " wasitaratisaw".

[r035198x]

Have you worked out your algorithm for it yet?

[JosAH]

An utterly naive algorithm would take O(n^2) steps: it checks all indexes j > i+1
whether substring s_i ... s_j is a palindrome or not. Cleverly in/decrementing
both index values would find larger palindromes first and cut off the search for
smaller palindromes; worst case it would still be a O(n^2) algorithm.

kind regards,

Jos