Aizu Online Judge 1203 Napoleon's Grumble

■1203 Napoleon's Grumble

回文の中心点jを0~n-1まで動かしながら，
c_j-i,…,c_j+i
c_j-i,…,c_j+i+1
が回文となる最大のiを探す．
片っ端から回文候補をリストに入れた後，冗長のものを省く．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  String s;  
17.   
18.  void run(){  
19.   for(; sc.hasNextLine();){  
20.    s=sc.nextLine();  
21.    solve();  
22.   }  
23.  }  
24.   
25.  void solve(){  
26.   s=s.toUpperCase().replaceAll("[^A-Z]", "");  
27.   int n=s.length();  
28.   TreeSet<String> set=new TreeSet<String>();  
29.   for(int j=0; j<n; j++){  
30.    int i;  
31.    for(i=0; j-i>=0&&j+i<n&&s.charAt(j-i)==s.charAt(j+i); i++);  
32.    i--;  
33.    if(i>=1){  
34.     set.add(s.substring(j-i, j+i+1));  
35.    }  
36.    for(i=0; j-i>=0&&j+i+1<n&&s.charAt(j-i)==s.charAt(j+i+1); i++);  
37.    i--;  
38.    if(i>=1){  
39.     set.add(s.substring(j-i, j+i+2));  
40.    }  
41.   }  
42.   for(Iterator<String> i=set.iterator(); i.hasNext();){  
43.    String s=i.next();  
44.    for(Iterator<String> j=set.iterator(); j.hasNext();){  
45.     String t=j.next();  
46.     if((s.length()+t.length())%2==0&&t.length()>s.length()){  
47.      int k=(t.length()-s.length())/2;  
48.      if(t.substring(k, t.length()-k).equals(s)){  
49.       i.remove();  
50.       break;  
51.      }  
52.     }  
53.    }  
54.   }  
55.   for(; !set.isEmpty();){  
56.    print(set.pollFirst());  
57.    if(!set.isEmpty()){  
58.     print(" ");  
59.    }  
60.   }  
61.   println("");  
62.  }  
63.   
64.  void debug(Object... os){  
65.   System.err.println(Arrays.deepToString(os));  
66.  }  
67.   
68.  void print(String s){  
69.   System.out.print(s);  
70.  }  
71.   
72.  void println(String s){  
73.   System.out.println(s);  
74.  }  
75.   
76.  public static void main(String[] args){  
77.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
78.   new Main().run();  
79.  }  
80. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 String s;

 void run(){
  for(; sc.hasNextLine();){
   s=sc.nextLine();
   solve();
  }
 }

 void solve(){
  s=s.toUpperCase().replaceAll("[^A-Z]", "");
  int n=s.length();
  TreeSet<String> set=new TreeSet<String>();
  for(int j=0; j<n; j++){
   int i;
   for(i=0; j-i>=0&&j+i<n&&s.charAt(j-i)==s.charAt(j+i); i++);
   i--;
   if(i>=1){
    set.add(s.substring(j-i, j+i+1));
   }
   for(i=0; j-i>=0&&j+i+1<n&&s.charAt(j-i)==s.charAt(j+i+1); i++);
   i--;
   if(i>=1){
    set.add(s.substring(j-i, j+i+2));
   }
  }
  for(Iterator<String> i=set.iterator(); i.hasNext();){
   String s=i.next();
   for(Iterator<String> j=set.iterator(); j.hasNext();){
    String t=j.next();
    if((s.length()+t.length())%2==0&&t.length()>s.length()){
     int k=(t.length()-s.length())/2;
     if(t.substring(k, t.length()-k).equals(s)){
      i.remove();
      break;
     }
    }
   }
  }
  for(; !set.isEmpty();){
   print(set.pollFirst());
   if(!set.isEmpty()){
    print(" ");
   }
  }
  println("");
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}