Calf Flac - USACO 1.3.3

calfflac - codetrick

It is said that if you give an infinite number of cows an infinite number of heavy-duty laptops (with very large keys), that they will ultimately produce all the world's great palindromes. Your job will be to detect these bovine beauties.

Ignore punctuation, whitespace, and case when testing for palindromes, but keep these extra characters around so that you can print them out as the answer; just consider the letters `A-Z' and `a-z'.
Find any largest palindrome in a string no more than 20,000 characters long. The largest palindrome is guaranteed to be at most 2,000 characters long before whitespace and punctuation are removed.

PROGRAM NAME: calfflac

INPUT FORMAT

A file with no more than 20,000 characters. The file has one or more lines. No line is longer than 80 characters (not counting the newline at the end).

SAMPLE INPUT (file calfflac.in)

Confucius say: Madam, I'm Adam.  

OUTPUT FORMAT

The first line of the output should be the length of the longest palindrome found. The next line or lines should be the actual text of the palindrome (without any surrounding white space or punctuation but with all other characters) printed on a line (or more than one line if newlines are included in the palindromic text). If there are multiple palindromes of longest length, output the one that appears first.

SAMPLE OUTPUT (file calfflac.out)

11  Madam, I'm Adam

http://code.antonio081014.com/2012/09/usaco-calf-flac.html
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/calfflac.java

 * 1st, String.substring will take much time.
 * 2nd, String.toLower will take much time. Don't translate to lower case
 * every time, just translate it at the very first beginning.
 * It takes me more than 36 hrs.
 * 
 * Time Complexity: O(N*M)
 * N is the length of the total string.
 * M is the length of the longest palindrome string.

    public String store;
    public int    max;
    int           From;
    int           To;

    public static void main(String[] args) throws Exception {
        calfflac main = new calfflac();
        main.solve();
        System.exit(0);
    }

    public void solve() throws Exception {
        BufferedReader br = new BufferedReader(new FileReader("calfflac.in"));
        BufferedWriter out = new BufferedWriter(new FileWriter("calfflac.out"));
        String strLine = "";
        String str;
        while ((str = br.readLine()) != null) {
            strLine += str + "\n";
        }
        max = 0;
        From = 0;
        String text = strLine.toLowerCase();
        int N = strLine.length();
        for (int i = 0; i < N; i++) {
            palindrom1(i, text, N);
            palindrom2(i, text, N);
        }
        out.write("" + max + "\n");
        for (int i = From; i <= To; i++)
            out.write(strLine.charAt(i));
        out.write("\n");
        // out.write(strLine.substring(From, To + 1) + "\n");
        out.close();
    }

    //Check for BBABB;
    public void palindrom1(int index, String s, int N) {
        int start = index;
        int end = index;
        int count = isAlpha(s.charAt(index)) ? 1 : 0;
        for (int i = index - 1, j = index + 1; i >= 0 && j < N;) {
            while (i >= 0 && isAlpha(s.charAt(i)) == false)
                i--;
            while (j < s.length() && isAlpha(s.charAt(j)) == false)
                j++;
            if (i < 0 || j >= N)
                break;
            if (s.charAt(i) != s.charAt(j)) {
                if (count > max) {
                    From = start;
                    To = end;
                    max = count;
                }
                return;
            }
            else {
                count += 2;
                start = i;
                end = j;
                i--;
                j++;
            }
        }
        if (count > max) {
            From = start;
            To = end;
            max = count;
        }
        // return count;
        // return Math.min(index, s.length() - index - 1) * 2 + 1;
    }
    
    //Check for BBAABB;
    public void palindrom2(int index, String s, int N) {
        int start = index;
        int end = index;
        int count = 0;
        for (int i = index, j = index + 1; i >= 0 && j < N;) {
            while (i >= 0 && isAlpha(s.charAt(i)) == false)
                i--;
            while (j < s.length() && isAlpha(s.charAt(j)) == false)
                j++;
            if (i < 0 || j >= N)
                break;
            if (s.charAt(i) != s.charAt(j)) {
                if (count > max) {
                    From = start;
                    To = end;
                    max = count;
                }
                return;
                // return 2 * (j - index - 1);
            }
            else {
                count += 2;
                start = i;
                end = j;
                i--;
                j++;
            }
        }
        if (max < count) {
            From = start;
            To = end;
            max = count;
        }
        // return count;
        // return Math.min(index + 1, s.length() - index - 1) * 2;
    }

Read full article from calfflac - codetrick