【 Algorithm 】 The longest common substring

If you have two strings STR and str2, find the longest common substring length in both strings.

For example: STR = ACBCBCEF, STR2 = ABCBCED, then the longest common substring of STR and STR2 is BCBCE, and the longest common substring length is 5.

Solution:

Set to 1 if the characters are the same, otherwise set to 0



Reduce the repeated calculation, arr [I] [j] = arr [I – 1] [1], the attention should be paid to the point is that when I = = 0 | | j = = 0 to set values directly.

Java code implementation:

Private static getLcs(String s1, String s2) {int maxLen = 0, maxEnd = 0; private static getLcs(String s1, String s2); int[][] arr = new int[s1.length()][s2.length()]; for (int i = 0; i < s1.length(); i++) { for (int j = 0; j < s2.length(); j++) { if (s1.charAt(i) == s2.charAt(j)) { if (i == 0 || j == 0) { arr[i][j] = 1; } else { arr[i][j] = arr[i - 1][j - 1] + 1; } } else { arr[i][j] = 0; } if (arr[i][j] > maxLen) { maxEnd = i; maxLen = arr[i][j]; } } } if (maxLen == 0) { return ""; } return s1.substring(maxEnd - maxLen + 1, maxEnd); }

Refer to the article for the longest common substring of two strings https://blog.csdn.net/qq_2580…