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

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

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

 

代码：

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

评论

1 楼 muyishuihan 2012-10-29  

Mark一下