最长公共子串

思路：
使用dp数组，当i=0||j=0时 c[i,j]=0，当xi=yj时,c[i,j]=c[i-1,j-1]+1，当xi!=yj时,c[i,j]=0。
  1 /**
  2  * @author: wooch
  3  * @create: 2020/02/12
  4  * 最长公共子串
  5  * 核心思路：
  6  * 使用dp数组
  7  * 当i=0||j=0时 c[i,j]=0
  8  * 当xi=yj时,c[i,j]=c[i-1,j-1]+1
  9  * 当xi!=yj时,c[i,j]=0
 10  */
 11 public class LongestCommonSubstring {
 12     public static void main(String[] args) {
 13         // 定义两个字符串
 14         String x = "abcde";
 15         String y = "cdcdeabc";
 16         System.out.println(longestCommonSubstring(x, y));
 17         lcs(x,y);
 18     }
 19 
 20     /**
 21      * the think way of the problem
 22      *
 23      * @param strX
 24      * @param strY
 25      */
 26     public static void lcs(String strX, String strY) {
 27         int lenX = strX.length();
 28         int lenY = strY.length();
 29         char[] chsX = strX.toCharArray();
 30         char[] chsY = strY.toCharArray();
 31         int[][] dpArray = new int[lenX + 1][lenY + 1];
 32 
 33         int maxLength = 0;
 34         int countSubString = 0;
 35         // 用于存储最长公共子串末尾元素索引的数组
 36         int[] lastCharSubString = new int[lenX];
 37 
 38 
 39         for (int i = 0; i < lenX + 1; i++) {
 40             for (int j = 0; j < lenY + 1; j++) {
 41                 if (i == 0 || j == 0) {
 42                     dpArray[i][j] = 0;
 43                 } else if (chsX[i - 1] == chsY[j - 1]) {
 44                     dpArray[i][j] = dpArray[i - 1][j - 1] + 1;
 45 
 46                     if (dpArray[i][j] > maxLength) {
 47                         maxLength = dpArray[i][j];
 48 
 49                         // 每一次最长公共子串长度更新, 重置索引数组, 重置个数
 50                         for (int k = 0; k < countSubString; k++) {
 51                             lastCharSubString[k] = 0;
 52                         }
 53                         countSubString = 1;
 54                         lastCharSubString[countSubString - 1] = i;
 55 
 56                         // 如果dpArray[i][j]==maxLength，则说明出现新的一个LCS
 57                         // 索引数组增加一个元素用于存储新LCS的索引
 58                         // 子串个数+1
 59                     } else if (dpArray[i][j] == maxLength) {
 60                         lastCharSubString[countSubString] = i;
 61                         countSubString++;
 62                     }
 63 
 64                 } else {
 65                     dpArray[i][j] = 0;
 66                 }
 67             }
 68         }
 69         // 打印动态规划表dpArray[i,j]
 70         System.out.println("动态规划表c[i,j]:");
 71         for (int j = 0; j < lenY + 1; j++) {
 72             for (int i = 0; i < lenX + 1; i++) {
 73                 System.out.print(dpArray[i][j] + "	");
 74             }
 75             System.out.println();
 76         }
 77 
 78         // 打印最长公共子串
 79         for (int i = 1; i <= countSubString; i++) {
 80             System.out.print("Longest Common Substring " + i + ": ");
 81             for (int j = maxLength; j > 0; j--) {
 82                 System.out.print(chsX[lastCharSubString[i - 1] - j]);
 83             }
 84             System.out.println();
 85         }
 86 
 87         System.out.println("Amount of Longest Common Substring: " + countSubString);
 88 
 89         System.out.println("Max length of Longest Common Substring: " + maxLength);
 90 
 91     }
 92 
 93     /**
 94      * only find the result of the problem
 95      *
 96      * @param strX
 97      * @param strY
 98      * @return
 99      */
100     public static int longestCommonSubstring(String strX, String strY) {
101         int lenX = strX.length();
102         int lenY = strY.length();
103         char[] chsX = strX.toCharArray();
104         char[] chsY = strY.toCharArray();
105         int[][] dpArray = new int[lenX + 1][lenY + 1];
106 
107         int maxLength = 0;
108 
109         for (int i = 0; i < lenX + 1; i++) {
110             for (int j = 0; j < lenY + 1; j++) {
111                 if (i == 0 || j == 0) {
112                     dpArray[i][j] = 0;
113                 } else if (chsX[i - 1] == chsY[j - 1]) {
114                     dpArray[i][j] = dpArray[i - 1][j - 1] + 1;
115                     maxLength = Math.max(maxLength, dpArray[i][j]);
116                 } else {
117                     dpArray[i][j] = 0;
118                 }
119             }
120         }
121 
122         return maxLength;
123     }
124 }
View Code