package 动态规划;
import java.util.Scanner;
public class LogestCommonZiXuLie
{

    public static void main(String[] args)
     {
      Scanner scan = new Scanner(System.in);
      while(scan.hasNextLine())
        {
          String str = scan.nextLine();
          String revStr = reverse(str);
          int lcs = getLongestCommonSeq(str, revStr);
          System.out.println("字符串长度: "+lcs);
        }
    }
  public static int getLongestCommonSeq(String str1, String str2)
   {
    int len1 = str1.length();
    int len2 = str2.length();

    int[][] c = new int[len1+1][len2+1];
    for(int i=0; i<=len1; i++)
       {
         c[i][0] = 0;
       }
    for(int j=0; j<=len2; j++)
       {
        c[0][j] = 0;
       }
             //先遍历横坐标在遍历纵坐标在回溯时就要比较左边和上边的值时如果左边小于上边就要横坐标自减
           //就是对应的下面的j--或者i--判断选其一
     for(int i=1; i<=len1; i++)
        {
           for(int j=1; j<=len2; j++)
              {
                char char1 = str1.charAt(i-1);//取得第一个字符串的其中一个
                char char2 = str2.charAt(j-1);//取出第二个字符串的每一个与前一个的字符串其中一个比较
                if(char1 == char2)
                    {
                     c[i][j] = c[i-1][j-1]+1;
                    }

               else{
                    c[i][j] = max(c[i][j-1], c[i-1][j]);
                   }
             //System.out.print(c[i][j]+" ");
             }
           //System.out.println();
     }

      //打印出公共子序列
       char str[]= new char[100];
       int index = c[len1][len2]-1;//最长公共子字符串保存的下标
       //System.out.println("index = "+index);
      System.out.print("子字符串为：");
       for (int i = len1,j = len2; i>0&&j>0;)
           {
             if(str1.charAt(i-1) == str2.charAt(j-1))
               {
                  str[index--] = str1.charAt(i-1);
                  //横纵坐标都自减的目的是因为围绕对角线的公共子字符串最长
                  i--;
                  j--;
                  System.out.print(str1.charAt(i));
                 //System.out.print(" "+str[index+1]+" --");
                }
             else
               {
             //比较c[i][j]左边和上边的两个值
              if(c[i][j-1]>c[i-1][j])
                     {
                       j--;
                      }else
                      {
                       i--;
                      }
                  }
          }
          System.out.println();
         return c[len1][len2];
 }
//求两个数得最大值,可以用包里的Math函数，
public static int max(int i1, int i2)
{
if(i1 > i2) return i1;
else return i2;
}
//求得字符串得反字符串，也可以用函数求得
public static String reverse(String str)
{
String reverseStr = "";
for(int i=str.length()-1; i>=0; i--){
reverseStr += str.charAt(i);
}
return reverseStr;
}

}

动态规划--之--最长公共子字符串