最长公共子序列和最长公共子串

 1 public class Solution {
 2 
 3     public static void main(String[] args) {
 4         String str1 = "12asdfa";
 5         String str2 = "we2rasdaswer";
 6 
 7         int result = longestCommonSubsequence(str1, str2);
 8         System.out.println(result);
 9 
10     }
11 
12     // LCS
13     public static int longestCommonSubsequence(String str1, String str2) {
14         int[][] matrix = new int[str1.length()+1][str2.length()+1];
15 
16         for(int i = 0; i < str1.length(); i++) {
17             matrix[i][0] = 0;
18         }
19 
20         for(int j = 0; j <= str2.length(); j++) {
21             matrix[0][j] = 0;
22         }
23 
24         for(int i = 1; i <= str1.length(); i++) {
25             for(int j = 1; j <= str2.length(); j++) {
26                 if(str1.charAt(i-1) == str2.charAt(j-1)) {
27                     matrix[i][j] = matrix[i-1][j-1] + 1;
28                 } else {
29                     matrix[i][j] = (matrix[i-1][j] >= matrix[i][j-1]?matrix[i-1][j]:matrix[i][j-1]);
30                 }
31             }
32         }
33 
34         return matrix[str1.length()][str2.length()];
35     }
36 }

 1 public class Solution {
 2     public static void main(String[] args) {
 3 
 4         String str1 = "abcdef";
 5         String str2 = "cde";
 6 
 7         int result = longestCommonSubstring(str1, str2);
 8         System.out.println(result);
 9     }
10 
11     public static int longestCommonSubstring(String str1, String str2) {
12         int len1 = str1.length();
13         int len2 = str2.length();
14         int result = 0;
15 
16         int[]][] c = new int[len1+1][len2+1];
17         for(int i = 0; i <= len1; i++) {
18             for(int j = 0; j <= len2l j++) {
19                 if(i == 1 || j == 1) {
20                     c[i][j] = 0;
21                 } else if(str1.charAt(i-1) == str2.charAt(j)) {
22                     c[i][j] = c[i-1][j-1] + 1;
23                     result = Math.max(result, c[i][j]);
24                 } else {
25                     c[i][j] = 0;
26                 }
27             }
28         }
29 
30         return result;
31     }
32 }