问题：有两个字符串str1和str2，求出两个字符串中最长公共字符串。
例如：“acbbsdef”和"abbsced"的最长公共字符串是“bbs”
算法思路：
1、把两个字符串分别以行和列组成一个二维矩阵。
2、比较二维矩阵中行和列对应的每个点的字符是否相同，是设置这个点为1，否设置这个点为0。
3、通过查找值为1的最长对角线来找到最长公共字符串。
通过上面str1和str2两个字符串,分别得出以行和列组成的一个二维矩阵如下图：

1. public class MaxStringDemo {
   
2. 
   
3.     public static void main(String[] args) {
   
4.         String aa = "abc123edf";
   
5.         String bb = "bc123jg";
   
6.         maxUtil2(aa, bb);
   
7.         System.out.println(maxUtil2(aa, bb));
   
8.     }
   
9. 
   
10.     public static StringBuilder maxUtil2(String str1, String str2) {
    
11.         //把字符串转成字符数组
    
12.         char[] arr1 = str1.toCharArray();
    
13.         char[] arr2 = str2.toCharArray();
    
14.         // 把两个字符串分别以行和列组成一个二维矩阵
    
15.         int[][] temp = new int[arr1.length][arr2.length];
    
16.         // 存储最长公共子串长度
    
17.         int length = 0;
    
18.         //start表明最长公共子串的起始点，end表明最长公共子串的终止点
    
19.         int end = 0;
    
20.         int start = 0;
    
21.         ////初始化二维矩阵中的第一行
    
22.         for (int i = 0; i < arr2.length; i++) {
    
23.             temp[0][i] = (arr1[0] == arr2[i]) ? 1 : 0;
    
24.         }
    
25.         //初始化二维矩阵中的第一列
    
26.         for (int j = 0; j < arr1.length; j++) {
    
27.             temp[j][0] = (arr2[0] == arr1[j]) ? 1 : 0;
    
28.         }
    
29.         //嵌套for循环：比较二维矩阵中每个点对应行列字符中否相等，相等的话值设置为1，否则设置为0
    
30.         for (int i = 1; i < arr1.length; i++) {
    
31.             for (int j = 1; j < arr2.length; j++) {
    
32.                 if (arr1[i] == arr2[j]) {
    
33.                     temp[i][j] = temp[i - 1][j - 1] + 1;
    
34. 
    
35.                     if (temp[i][j] > length) {
    
36.                         length = temp[i][j];
    
37.                         end = j;
    
38.                     }
    
39.                 } else
    
40.                     temp[i][j] = 0;
    
41. 
    
42.             }
    
43.         }
    
44.         //求出最长公共子串的起始点
    
45.         start=end-length+1;
    
46.         StringBuilder sb=new StringBuilder();
    
47.         //通过查找出值为1的最长对角线就能找到最长公共子串
    
48.         for (int j = start; j < end+1; j++) {
    
49.             sb.append(arr2[j]);
    
50.         }
    
51. 
    
52.         return sb;
    
53.     }
    
54. 
    
55. }

复制代码

到这里，求出两个字符串的最长公共字符串的问题已经解决！

很好- -思路很清晰

赞一个。。。加油。。。

1. package cn.itcast.string.demo;
   
2. 
   
3. /*
   
4. * 题目：两个字符串的最大相同子串
   
5. * "ahhfhosnfdkhcihfa"
   
6. * "fdafakjdhosnfgnao"
   
7. * 思路：先按照一定顺序求一个字符串的子串，然后判断另一个字符串是否包含子串，只要第一次包含，就是最大的子串。
   
8. *
   
9. */
   
10. public class StringTest2 {
    
11. 
    
12.         public static void main(String[] args) {
    
13.                 String s1 = "ahhfhosnfdkhcihfa";
    
14.                 String s2 = "fdafakjdhosnfgn";
    
15.                 String s = getMaxSubstr(s1, s2);
    
16.                 System.out.print("s=" + s);
    
17. 
    
18.         }
    
19. 
    
20.         public static String getMaxSubstr(String s1, String s2) {
    
21.                 // 判断字符串的长度
    
22.                 String temp = null;
    
23.                 if (s2.length() >= s1.length())
    
24.                         temp = s1;
    
25.                 s1 = s2;
    
26.                 s2 = temp;
    
27.                 // 由长到短的顺序获取短字符串的所有子串
    
28.                 for (int i = 0; i < s2.length(); i++) {
    
29.                         for (int y = 0, z = s2.length() - i; z != s2.length() + 1; y++, z++) {
    
30.                                 String sub = s2.substring(y, z);
    
31.                                 // 判断长字符串是否包换子串
    
32.                                 if (s1.contains(sub))
    
33.                                         return sub;
    
34.                         }
    
35. 
    
36.                 }
    
37.                 return null;
    
38. 
    
39.         }
    
40. 
    
41. }
    

复制代码

老毕的视频中也有一个方法，先按照一定顺序求较短字符串的所有子串，然后判断另一个字符串是否包含子串，第一次包含，就是最大的子串。

这方法思路很好啊，学习啦！

很清晰的

学习了，相当新奇的思路

不错不错，学习了