A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 李春江 中级黑马   /  2014-11-2 12:27  /  1069 人查看  /  7 人回复  /   1 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 李春江 于 2014-11-2 12:31 编辑

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

  1. public class MaxStringDemo {

  2.     public static void main(String[] args) {
  3.         String aa = "abc123edf";
  4.         String bb = "bc123jg";
  5.         maxUtil2(aa, bb);
  6.         System.out.println(maxUtil2(aa, bb));
  7.     }

  8.     public static StringBuilder maxUtil2(String str1, String str2) {
  9.         //把字符串转成字符数组
  10.         char[] arr1 = str1.toCharArray();
  11.         char[] arr2 = str2.toCharArray();
  12.         // 把两个字符串分别以行和列组成一个二维矩阵
  13.         int[][] temp = new int[arr1.length][arr2.length];
  14.         // 存储最长公共子串长度
  15.         int length = 0;
  16.         //start表明最长公共子串的起始点,end表明最长公共子串的终止点
  17.         int end = 0;
  18.         int start = 0;
  19.         ////初始化二维矩阵中的第一行
  20.         for (int i = 0; i < arr2.length; i++) {
  21.             temp[0][i] = (arr1[0] == arr2[i]) ? 1 : 0;
  22.         }
  23.         //初始化二维矩阵中的第一列
  24.         for (int j = 0; j < arr1.length; j++) {
  25.             temp[j][0] = (arr2[0] == arr1[j]) ? 1 : 0;
  26.         }
  27.         //嵌套for循环:比较二维矩阵中每个点对应行列字符中否相等,相等的话值设置为1,否则设置为0
  28.         for (int i = 1; i < arr1.length; i++) {
  29.             for (int j = 1; j < arr2.length; j++) {
  30.                 if (arr1[i] == arr2[j]) {
  31.                     temp[i][j] = temp[i - 1][j - 1] + 1;

  32.                     if (temp[i][j] > length) {
  33.                         length = temp[i][j];
  34.                         end = j;
  35.                     }
  36.                 } else
  37.                     temp[i][j] = 0;

  38.             }
  39.         }
  40.         //求出最长公共子串的起始点
  41.         start=end-length+1;
  42.         StringBuilder sb=new StringBuilder();
  43.         //通过查找出值为1的最长对角线就能找到最长公共子串
  44.         for (int j = start; j < end+1; j++) {
  45.             sb.append(arr2[j]);
  46.         }

  47.         return sb;
  48.     }

  49. }
复制代码


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

评分

参与人数 1技术分 +1 收起 理由
杨佳名 + 1 很给力!

查看全部评分

7 个回复

倒序浏览
很好- -思路很清晰
回复 使用道具 举报
赞一个。。。加油。。。
回复 使用道具 举报
  1. package cn.itcast.string.demo;

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

  10.         public static void main(String[] args) {
  11.                 String s1 = "ahhfhosnfdkhcihfa";
  12.                 String s2 = "fdafakjdhosnfgn";
  13.                 String s = getMaxSubstr(s1, s2);
  14.                 System.out.print("s=" + s);

  15.         }

  16.         public static String getMaxSubstr(String s1, String s2) {
  17.                 // 判断字符串的长度
  18.                 String temp = null;
  19.                 if (s2.length() >= s1.length())
  20.                         temp = s1;
  21.                 s1 = s2;
  22.                 s2 = temp;
  23.                 // 由长到短的顺序获取短字符串的所有子串
  24.                 for (int i = 0; i < s2.length(); i++) {
  25.                         for (int y = 0, z = s2.length() - i; z != s2.length() + 1; y++, z++) {
  26.                                 String sub = s2.substring(y, z);
  27.                                 // 判断长字符串是否包换子串
  28.                                 if (s1.contains(sub))
  29.                                         return sub;
  30.                         }

  31.                 }
  32.                 return null;

  33.         }

  34. }
复制代码
老毕的视频中也有一个方法,先按照一定顺序求较短字符串的所有子串,然后判断另一个字符串是否包含子串,第一次包含,就是最大的子串。
回复 使用道具 举报
这方法思路很好啊,学习啦!
回复 使用道具 举报
很清晰的
回复 使用道具 举报
学习了,相当新奇的思路
回复 使用道具 举报
WakeUp 来自手机 中级黑马 2014-11-2 17:33:41
8#
不错不错,学习了
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马