Ok, here is an example input file:
100
ajcfeafjegjccehhfeibcijdgiacbafbbaifagegcfigciehce agcjjaibdbbadeadjbjgjddiafggeaaegcghfgjihcicjjgach
100
gbdcbfjjbejbahfihaeiaecjgbaecccaffcjacidiaeajbjgcf eejjdgafacjedfbhedbegjeccgebciijciiigididddiaehgij
101
agihjadddhdcgfcgfihjgaebaeihaigcehjdjcidabhijbfejc fhejjefjdfhaibjjhicfdejacabjgcbcahdbbjafghheagehei f
101
icgaggegcijgahababdhhcgefcacjajjefbadhiigaeghgajhf jhifddidhjdhihebjajiifiedhbdiajhjjdcedhbccacbhfbhe b
0
Ps: The sequence is entirely on a single line, but for some reason it got split here.
Initially I went with the break around the biggest pal method, but it soon showed it weakness when it received the String ggeaaegfg into g, geaaeg, f, g instead of gg, eaae, gfg. So I had to creat a method to find if the biggest String was the best choice. Yet it still fails on number 3, where it finds 85 instead of 84.
Code:
import java.io.*;
public class pal2 {
public static void main(String args[]) throws IOException {
// Preparing
BufferedReader pal = new BufferedReader(new FileReader("pal.in"));
PrintWriter palO = new PrintWriter(new FileWriter("pal.out"));
String read = pal.readLine();
int cont = 1;
// Reading the file
while (Integer.parseInt(read) != 0) {
// Reading
read = pal.readLine();
// Writing teste x on file
palO.println("Test " + cont);
// Caling the method that will do the job
int a = getNum(read);
palO.println(a);
palO.println();
// Increasing pal counter and reading next number
cont++;
read = pal.readLine();
}
pal.close();
palO.close();
} // p s v m (S a)
// Recursive Method to discover the number of parts needed
public static int getNum(String p) {
// Always begin with one, since this is the least amount of parts the
// given string will have
int x = 1;
// Do the silly test, is it a pal?
if (isPalindrome(p))
return x;
// if not, Finding an optimized pal
String pal = findBestPal(p, true);
// No pals on the String? X becomes it's size
if (pal.length() == 0)
x = p.length();
// If there are..
else {
// Find the break point
int separador = p.indexOf(pal);
// Call yourself again using the left and rigth String
if (separador > 0) {
x += getNum(p.substring(0, separador));
}
if (separador + pal.length() < p.length()) {
x += getNum(p.substring(separador + pal.length()));
}
}
// Return the value you found
return x;
} // getNum
// This method chooses the best pal around which the String has to the split
public static String findBestPal(String p, boolean optimize) {
// Strings for the biggest and second biggest
String biggest = "";
String secBiggest = "";
// Searching through the given String
for (int limitLeft = 0; limitLeft < p.length() - 1; limitLeft++) {
String temp = "";
// Keep increasing the right limit and verifying
for (int limitRight = limitLeft + 1; limitRight < p.length(); limitRight++) {
// Cheking if the current substring is a pal
if (isPalindrome(p.substring(limitLeft, limitRight + 1))) {
temp = p.substring(limitLeft, limitRight + 1);
// Optimizing to make sure this is the best String
if (optimize == true)
temp = optimizePal(temp, p);
// If the temp you found is bigger then the previous one
// than replace it
if (temp.length() > biggest.length()) {
secBiggest = biggest;
biggest = temp;
}
// Dealing with a situation where aacac was split in a, aca,
// c
else if (temp.length() == biggest.length()) {
// If the biggest pal is using part of the second
// biggest pal, and you find another pal of equal size
// than replace it.
if (p.indexOf(secBiggest) + secBiggest.length() > p
.indexOf(biggest)
&& biggest.indexOf(secBiggest) == -1
|| p.indexOf(secBiggest) < p.indexOf(biggest)
+ biggest.length()
&& biggest.indexOf(secBiggest) == -1)
biggest = temp;
}
}
}
}
return biggest;
}
// Is the String a pal?
public static boolean isPalindrome(String p) {
for (int i = 0; i < p.length() / 2; i++) {
if (p.charAt(i) != p.charAt(p.length() - i - 1)) {
return false;
}
}
return true;
}
// Méthod to make sure the best pal is being choosen
public static String optimizePal(String temp, String p) {
// Limits to search for new pals
int position = p.indexOf(temp);
int limitLeft = position + temp.length() / 2 - 1;
int limitLeftExt = position;
int limitRight = position + temp.length() / 2 + 1;
int limitRightExt = position + temp.length() - 1;
// New pals
String biggestLeft = "";
String biggestRight = "";
// String with the temporary pal
String tempPal = "";
// Searching the right and left ones
biggestLeft = searchLeft(p, limitLeft, limitLeftExt);
biggestRight = searchRight(p, limitRight, limitRightExt);
// If the pal you found has letters that are part of a bigger pal ignore
// it
if (searchLeft(p, limitLeftExt - 1, limitLeftExt).length() > biggestLeft
.length())
return temp;
if (searchRight(p, limitRightExt, limitRightExt + 1).length() > biggestRight
.length())
return temp;
// Resizing the String after the new pals have been removed from it and
// then find the new pal
int positionLeft = p.indexOf(biggestLeft);
int positionRight = (p.substring(limitRight)).indexOf(biggestRight)
+ limitRight;
if (biggestRight.length() >= 2 && biggestLeft.length() >= 2)
temp = findBestPal(p.substring(positionLeft + biggestLeft.length(),
positionRight), false);
if (temp.length() > 0) {
return temp;
}
return biggestRight;
}
private static String searchRight(String p, int limitRight,
int limitRightExt) {
String biggestRight = "";
for (int limitPrinc = limitRight; limitPrinc <= limitRightExt; limitPrinc++) {
for (int limitSec = limitPrinc + 1; limitSec < p.length(); limitSec++) {
String pal = p.substring(limitPrinc, limitSec + 1);
if (isPalindrome(pal) && pal.length() > biggestRight.length())
biggestRight = pal;
}
}
return biggestRight;
}
private static String searchLeft(String p, int limitLeft, int limitLeftExt) {
String biggestLeft = "";
for (int limitPrinc = limitLeft; limitPrinc >= limitLeftExt; limitPrinc--) {
for (int limitSec = limitPrinc - 1; limitSec > 0; limitSec--) {
String pal = p.substring(limitSec, limitPrinc + 1);
if (isPalindrome(pal) && pal.length() > biggestLeft.length())
biggestLeft = pal;
}
}
return biggestLeft;
}
} // public class pal