一道简单的求最大相似字串的笔试题

今天做了一道简单的笔试题，不过由于当时面对一个不是很友好的面试官有点小紧张，加之时间也比较紧，所以现场只写了个类似下面的代码（写在纸上的那个是不可运行的）。

题目是：求两个字串中的最长相似字串，如字串"erdkhjghj" 和 字串"gdfdghdkhjghkjljhhdr"中的最长相识字串是“dkhjgh”。

不知道大家有没有更好的方法。

		String s1 = "erdkhjghj";
		String s2 = "gdfdghdkhjghkjljhhdr";
		int n = 0;
		for (int i = s1.length(); i > 0; i--) {
			for (int j = 0; j < (s1.length() - i); j++) {
				if (s2.indexOf(s1.substring(j, j + i)) > 0) {
					n = i;
					System.out.println(s1.substring(j, j + i) + " - " + n);
					break;
				}
			}
			if (n > 0) {
				break;
			}
		}

楼主，你的代码我运行了一下，貌似是错误的。比如Str1=“123”，str2=“1234”
改正的代码如下：
String s1 = "erdkhjghj";  
String s2 = "gdfdghdkhjghkjljhhdr";  
int n = 0;  
for (int i = s1.length(); i > 0; i--) {  
    for (int j = 0; j <=(s1.length() - i); j++) {  
        if (s2.indexOf(s1.substring(j, j + i)) > -1) {  
            n = i;  
            System.out.println(s1.substring(j, j + i) + " - " + n);  
            break;  
        }  
    }  
    if (n > 0) {  
        break;  
    }  
} 

如果用递归，可能代码会简单得多

经典的求最长公共子序列,估计面试官是想考你LCS算法.
老实说,我觉得这个不算是"简单"了.

楼主的写法的确有点问题，二楼更正了。。。

顺着楼主的思路又实现了一下，会不会重复造轮子了！

 public static String maxLike(String s1, String s2) {
	    	  String tempStr;
	    	  if (s1.length() > s2.length()) {
	    		  tempStr = s2;
	    		  s2 = s1;
	    		  s1 = tempStr;
	    	  }
	    	  
	    	  for (int subLength = s1.length(); subLength > 0; subLength --) {
	    		  for (int start = 0; start<=s1.length()-subLength; start++) {
	    			  String substring = s1.substring(start, subLength+start);
	    			  if (s2.indexOf(substring) > -1) {
	    				  return substring;
	    			  }
	    		  }
	    	  }
	    	  
	    	  return "";
	      }

  

最大子序列和

   

比较土的一种写法:

    
    public String getMaxLike() {
        String str1 = "erdkhjghj";
        String str2 = "gdfdghdkhjghkjljhhdr";
        int len = str1.length();
        String maxLike = "";
        for (int i = 0; i < len; i++) {
            for (int j = len; j > i; j--) {
                String maxLikeTemp = str1.substring(i, j);
                if (str2.indexOf(maxLikeTemp) != -1 && maxLikeTemp.length() > maxLike.length()) {
                    maxLike = maxLikeTemp;
                }
            }
        }
        return maxLike;
    }