`
功夫小当家
  • 浏览: 182923 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

求两个字符串的最长公共子串 (字母必须相邻)

阅读更多

上一篇《求最长公共子串(可以不相邻)》的另一种变换题目,这个相对于上一篇,稍稍简单,不过这个算法的时间复杂度不太好,更简单的算法,有时间我再整理下。

问题:求最长公共子串,字符必须相邻。

 

代码:

public class common {

 public static void findCommon(String s1, String s2) {
  int i;//第一个游标从0 ~ length-1游走
  int j;//第二个游标从i+1 ~ length-1 游走
  String same = "";
  for (i = 0; i < s1.length(); i++) {
   for (j = i; j < s1.length(); j++) {
    String sub = s1.substring(i, j);//截取str1的子串
    //判断str2里是否有该子串,如果有该字串的长度是否比之前得到的公共子串长度大?若大,则替换same。
    if ((s2.indexOf(sub) != -1) && sub.length() > same.length()) {
     same = sub;
    }
   }
  }
  System.out.println(same);
 }

 public static void main(String[] args) {
  String s1 = "abcdefghigjaaaaa";
  String s2 = "xyzabcdefigjaaaa";
  common.findCommon(s1, s2);
 }
}

0
2
分享到:
评论
1 楼 muyishuihan 2012-10-29  
Mark一下

相关推荐

Global site tag (gtag.js) - Google Analytics