黑马程序员技术交流社区

标题: 求出两个字符串的最长公共字符串 [打印本页]
作者: 李春江    时间: 2014-11-2 12:27
标题: 求出两个字符串的最长公共字符串
本帖最后由 李春江 于 2014-11-2 12:31 编辑

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

  1. public class MaxStringDemo {

  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.     }

  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;

  35.                     if (temp[i][j] > length) {
  36.                         length = temp[i][j];
  37.                         end = j;
  38.                     }
  39.                 } else
  40.                     temp[i][j] = 0;

  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.         }

  52.         return sb;
  53.     }

  55. }
复制代码


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

作者: 冥夜    时间: 2014-11-2 12:48
很好- -思路很清晰
作者: 微笑凡    时间: 2014-11-2 12:51
赞一个。。。加油。。。
作者: yaodd321    时间: 2014-11-2 14:39
  1. package cn.itcast.string.demo;

  3. /*
  4. * 题目：两个字符串的最大相同子串
  5. * "ahhfhosnfdkhcihfa"
  6. * "fdafakjdhosnfgnao"
  7. * 思路：先按照一定顺序求一个字符串的子串，然后判断另一个字符串是否包含子串，只要第一次包含，就是最大的子串。
  8. *
  9. */
  10. public class StringTest2 {

  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);

  18.         }

  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.                         }

  36.                 }
  37.                 return null;

  39.         }

  41. }
复制代码
老毕的视频中也有一个方法，先按照一定顺序求较短字符串的所有子串，然后判断另一个字符串是否包含子串，第一次包含，就是最大的子串。
作者: lighter    时间: 2014-11-2 15:31
这方法思路很好啊，学习啦！
作者: relice    时间: 2014-11-2 16:58
很清晰的
作者: wzg1015    时间: 2014-11-2 17:02
学习了，相当新奇的思路
作者: WakeUp    时间: 2014-11-2 17:33
不错不错，学习了



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2