/*
 * %W %E% Salvatore Desiano
 *
 * Copyright (c) 1997 Salvatore Domenick Desiano
 */

package solutions;

import java.io.*;
import java.util.*;

/** 
 * Reports a sorted list of all non-redundant palindromes of length
 * three or greater on each line of input from standard input. Lines,
 * input, files, and palindromes are defined in the same way as in
 * prog1.java.<p>
 *
 * Output consists of a sorted list followed by a line of dashses. A
 * redundant palindrome is defined as any that
 * <ol>
 * <li>occurs more than oncee in the input string.</li>
 * <li>is the center of another, longer palindrome with a portion of each
 *    end chopped off.</li></ol><p>
 *
 * See <a href="#main(java.lang.String[])">main</a> for the cool part of 
 * this program.<p>
 *
 * @author Salvatore Domenick Desiano
 * @version 1.00, 02/24/98
 * @see SortedStrings
 */

public class subpal {
  /* This class uses the SortedStrings class, defined below, to hold and
   * sort the palindromes before they are printed. Palindromes that
   * occur more than once are weeded out by SortedStrings.insert()
   */

  /**
    * Performs the search for palindromes in each line of input,
    * stores them in a SortedStrings instance, and prints them
    * out. The cool part is how the palindromes are found:
    * subpal.main() scans the input from left to right. At each
    * character, checks for odd and even palindromes. Odd palindromes
    * are checked by growing outward to the left and right,
    * incrementing so long as the outmost characters match. In this
    * way, the largest palindrome centered on the current character is
    * found. Even palindromes are found by the same method, starting
    * only if the current and next characters match, and then fanning
    * out to both sides. This is O(n), where n is the number of
    * palindromes in the string!  
    */
  public static void main(String[] args) {

    String         input;	// Input buffer
				// Buffer for striped input
    StringBuffer   clean = new StringBuffer();
				// Sorted list of found palindromes
    SortedStrings  palindromes = new SortedStrings();
				// Buffered reader on standard input
    BufferedReader brInput = new BufferedReader(new InputStreamReader(System.in));


    try {
				// Loop through lines of input
      while (( input = brInput.readLine()) != null ) {
	clean.setLength(0);	// Clear last line's stripped buffer
	palindromes.empty();	// Clear last line's palindrome list

				// Strip input and deposit in clean
	for ( int i = 0; i < input.length(); i++ ) 
	  if (Character.isLetter(input.charAt(i)))
	    clean.append(Character.toLowerCase(input.charAt(i)));

				// Scan string, left to right. No
				// reason to check first or last
				// character, as they can't be the
				// center of a palindrome of length > 3
	for ( int i = 1; i < clean.length() - 1; i ++ ) {
	  int j;		// Counter for fanning out

				// Grow odd palindromes
	  for ( j = 1; (j<=i)&&((i+j)<clean.length()); j++ )
	    if ( clean.charAt(i-j) != clean.charAt(i+j) )
	      break;
				// Record the palindrome if it's three
				// or more characters
	  if ( j > 1 ) palindromes.insert(clean.toString().substring(i-j+1,i+j));

				// Grow even palindromes
	  if ( clean.charAt(i) == clean.charAt(i+1) ) {
	    for ( j = 1; (j<=i)&&((i+j+1)<clean.length()); j++ )
	      if ( clean.charAt(i-j) != clean.charAt(i+j+1) )
		break;
				// Record palindrome if it's long
				// enough
	    if ( j > 1 ) palindromes.insert(clean.toString().substring(i-j+1,i+j+1));

	  }
	}
				// Print out the found palindromes
	palindromes.dump();
	System.out.println("-------");
      }
    }
				// BuferredStream.readLine() throws an
				// IOException
    catch ( IOException ioe ) {
      System.err.println("IO error: " + ioe );
      ioe.printStackTrace();
    }
  }
}

/**
 * Holds a sorted list of strings. Pretty simple.
 *
 * @author Salvatore Domenick Desiano
 * @version 1.00, 02/24/98
 * @see java.util.Vector
 */

public class SortedStrings {

  /* Uses a vector to hold the sorted list of strings. Not very
   * efficient, but we only implement SortedStrings.insert(), so it
   * runs in O(n). Also, Vector takes care of all of our space
   * worries.
   */

  /**
   * The vector where the strings are stored. Initializes when the
   * SortedString is created.
   */
  private Vector list = new Vector();

  /**
   * Empties the list of strings.
   */
  public void empty() {
    list.setSize(0);
  }

  /**
   * Inserts a new string into it's place, lexographically sorted.
   *
   * @param  toInsert   the String to insert
   */
  public void insert ( String toInsert ) {
    /* We use a simple left-to-right scan of the vector to find the
     * new string's place.
     */

    int i = 0;
    for ( i = 0; (i < list.size()) && (toInsert.compareTo((String)list.elementAt(i))>0); i++ );
    if ( i == list.size() ) {	// can't compare
      list.insertElementAt(toInsert,i);
    } else if ( toInsert.compareTo((String)list.elementAt(i)) != 0) {
      list.insertElementAt(toInsert,i);
    }
  }


  /**
   * Prints the sorted list of strings
   */
  public void dump() {
    for ( int i = 0; i < list.size(); i++ )
      System.out.println(list.elementAt(i));
  }
}