Palindrome Detector: A palindrome is a phrase that reads the same forwards as it

Question

Palindrome Detector: A palindrome is a phrase that reads the same forwards as it does backwards. For example, "a man, a plan, canal, Panama." is a palindrome. Ignore white space and punctuation. Write a program that uses a stack to check for palindromes in each line of a text file. The main method should be in a class called FindPalindromes.java.The text file should be provided as a command line argument (remember String[] args from main). Try your program on the example text file, palindromes.txt in a new window. Your program should output the palindromes that it finds in the document. For example:

java FindPalindromes palindromes.txt

"a man, a plan, a canal, Panama" is a palindrome.

"Don't nod" is a palindrome.

"Taco Cat!" is a palindrome.

You must write your own MyStack class for this problem. It must be generic, in the sense that you should be able to use this stack with any type of object. Don't use the built in Stack, instead build your stack from java.util.LinkedList. Do not use the builtin push/pop methods from LinkedList.

palindromes.txt
Are the following lines palindromes?
A man, a plan, a canal, Panama.
This line is not a palindrome
Don't nod
The next one might be my favorite
Taco Cat!
Another non-palindrome
Rats live on no evil star.
If your program finds this line, it's not working
Neil, a trap! Sid is part alien!
Step on no pets.
Dammit, I'm mad!
Madam, I'm Adam.
Madam, in Eden, I'm Adam.
Rise to vote, sir.
aabbccbb
If I had a hi-fi
Yo, banana boy!
Do geese see God?
No devil lived on.
Ah, Satan sees Natasha.
Lewd did I live & evil I did dwel!
A dog, a panic in a pagoda
Was it a cat I saw?
Was it a car or a cat I saw?
A Toyota's a Toyota.
Another non-palindrome
No lemons, no melon
Now I see bees, I won.
Ma is as selfless as I am.
Nurse, I spy gypsies-run!
The next one isn't as cool as the Panama one
A dog, a plan, a canal, pagoda
Was it Eliot's toilet I saw?
Some of these are hilarious. Papaya war?!
No, sir, away! A papaya war is on!
Go hang a salami, I'm a lasagna hog.
I, madam, I made radio! So I dared! Am I mad? Am I?
Swap God for a janitor, rot in a jar of dog paws.
Eva, can I see bees in a cave?
Not a palindrome
So many dynamos!
Red rum, sir, is murder.

Explanation / Answer

package com.string;
public class PalindromeSubstring {
public int PalindromeSubstringEasy(char arr[]) {
int substring = 1;
for (int i = 0; i < arr.length; i++) {
int x, y;
int palindrome;
x = i;
y = i + 1;
palindrome = 0;
while (x >= 0 && y < arr.length && arr[x] == arr[y]) {
x--;
y++;
palindrome += 2;
}
substring = Math.max(substring, palindrome);
x = i - 1;
y = i + 1;
palindrome = 1;
while (x >= 0 && y < arr.length && arr[x] == arr[y]) {
x--;
y++;
palindrome += 2;
}
substring = Math.max(substring, palindrome);
}
return substring;
}
public int PalindromicSubstringLinear(char input[]) {
int index = 0;
char newInput[] = new char[2*input.length + 1];
for(int i=0; i < newInput.length; i++) {
if(i % 2 != 0) {
newInput[i] = input[index++];
} else {
newInput[i] = '$';
}
}
int T[] = new int[newInput.length];
int start = 0;
int end = 0;
for(int i=0; i < newInput.length; ) {
while(start >0 && end < newInput.length-1 && newInput[start-1] == newInput[end+1]) {
start--;
end++;
}
T[i] = end - start + 1;

if(end == T.length -1) {
break;
}
int newCenter = end + (i%2 ==0 ? 1 : 0);

for(int j = i + 1; j <= end; j++) {
T[j] = Math.min(T[i - (j - i)], 2 * (end - j) + 1);
if(j + T[i - (j - i)]/2 == end) {
newCenter = j;
break;
}
}
i = newCenter;
end = i + T[i]/2;
start = i - T[i]/2;
}
int max = Integer.MIN_VALUE;
for(int i = 0; i < T.length; i++) {
int val;
val = T[i]/2;
if(max < val) {
max = val;
}
}
return max;
}

public int PalindromeDynamic(char []str){
boolean T[][] = new boolean[str.length][str.length];
  
for(int i=0; i < T.length; i++){
T[i][i] = true;
}
  
int max = 1;
for(int l = 2; l <= str.length; l++){
int len = 0;
for(int i=0; i < str.length-l+1; i++){
int j = i + l-1;
len = 0;
if(l == 2){
if(str[i] == str[j]){
T[i][j] = true;
len = 2;
}
}else{
if(str[i] == str[j] && T[i+1][j-1]){
T[i][j] = true;
len = j -i + 1;
}
}
if(len > max){
max = len;
}
}
}
return max;
}

public static void main(String args[]) {
PalindromeSubstring lps = new PalindromeSubstring();
System.out.println(lps.PalindromicSubstringLinear("a man, a plan, canal, Panama".toCharArray()));
   }

}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.