算法：最长回文子串详解

最近面试对于算法自从ACM后就再也没有碰过了，还有就是现在已经从C转为JAVA了，编程的方式真的有时候不一样。

先上代码吧，从网上搜的很多代码我发现很多要不就不是很对，所以自己决定写了一个。

/** * 最长回文子串 * @param args */     Scanner sc=new Scanner(System.in);     String inputStr=sc.nextLine();     char[] input=inputStr.toCharArray();     int max=0;int indexb=0,indexe=0,tempindex=0,tempindexe=0;     for (int i = 0; i < input.length; i++) {         int count=0;       for (int j = input.length-1; j >i; j--) {             if(input[i]==input[j]) {               int begin=i;int end=j;               while(begin<=end) {                   if(input[begin]==input[end]) {                       begin++;                       end--;                   }else break;                                  }//end while               if(begin<end)                   continue;               else  {                   count=j-i+1;                   tempindex=i;tempindexe=j;                   break;               }                          }            }//end for j       if(count>max) {           max=count;           indexb=tempindex;           indexe=tempindexe+1;       }                       }//end for i     System.out.println(inputStr.substring(indexb,indexe));     System.out.println(max); }  

这是一个怎样的过程呢？最好还是开启单步调试及可以看明白，举个例子abbabb

先选i=0 即a  然后从后往前扫直到

input[i]==input[j]然后再以 i 和临时的j作为begin和end ,鉴别这个字串是否是回文子串

while(begin<=end) {

if(input[begin]==input[end]) {

begin++; end--; }

else break;

}//end while

if(begin<end)

continue;

else {

count=j-i+1; tempindex=i;tempindexe=j; 

break;//这个break特别重要

}

为什么说这个break非常重要呢？是因为按道理来说因为是从后往前扫描的，如果这个字串是回文字串的话那么就不用再从j后面的下标开始了，因为当前肯定是最长的了