fork download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. //import java.util.Arrays;
  5.  
  6.  
  7. class AIBOHP {
  8. static int ans[][];
  9. 	/**
  10. 	 * @param args
  11. 	 * @throws IOException 
  12. 	 * @throws NumberFormatException 
  13. 	 */
  14. 	public static void main(String[] args) throws NumberFormatException, IOException {
  15. 		// TODO Auto-generated method stub
  16. BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  17. int t=Integer.parseInt(br.readLine());
  18. StringBuilder sbu=new StringBuilder();
  19. while(t-->0){
  20. 	//StringBuilder xx=new StringBuilder();
  21. 	//for(int i=0;i<6100;i++)xx.append("a");
  22. 	StringBuilder sb=new StringBuilder(br.readLine());
  23. 	//StringBuilder sb=new StringBuilder(xx);
  24. 	String rev=sb.reverse().toString();
  25. 	//System.out.println(sb+" "+rev);
  26. 	sbu.append(sb.length()-LCS(sb.reverse().toString(), rev)).append("\n");
  27. }
  28. 	System.out.println(sbu);
  29. 	}
  30. public static int LCS(String a,String b){
  31. 	ans=new int[a.length()+1][b.length()+1];
  32. 	for(int i=1;i<ans.length;i++){
  33. 		for(int j=1;j<ans[i].length;j++){
  34. 			if(a.charAt(i-1)==b.charAt(j-1)){
  35. 				ans[i][j]=ans[i-1][j-1]+1;
  36. 			}
  37. 			else ans[i][j]=Math.max(ans[i-1][j],ans[i][j-1]);
  38. 		}
  39. 	}
  40. 	//for(int i=0;i<ans.length;i++)System.out.println(Arrays.toString(ans[i]));
  41. 	return ans[a.length()][b.length()];
  42. }
  43. }
  44.  
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
1
fft
stdout
copy 
1
https://ideone.com/i2fDhh
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!