今天碰到一个面试题目：求N个字符串中的最大公子串

今天碰到一个面试题目：求N个字符串中的最大公子串，比如：
1、abcde
2、abefg
3、werabc
这三个字符串的最大公子串是ab
我简单写个了程序，用的多层for循环，不知道大家有没有更好的办法

public class Test {

	public String getStr(List<String> strList){
		int length = 0;
		String sub = "";
		String result = null;
		for (int i = 0; i < strList.get(0).length(); i++) {
			for (int j = i; j < strList.get(0).length(); j++) {
				sub += strList.get(0).charAt(j);
				if(sub.length() > length){
					if(this.contains(strList,sub)){
						result = sub;
						length = sub.length();
					}else{
						sub = "";
						break;
					}
				}
			}
		}
		return result;
	}
	
	private boolean contains(List<String> strList,String sub){
		for (int i = 1; i < strList.size(); i++) {
			if(!strList.get(i).contains(sub)){
				return false;
			}
		}
		return true;
	}
	
	public static void main(String[] args) {
		List<String> list = new ArrayList();
		list.add("aaaabc");
		list.add("defaaade");
		list.add("ghtaaade");
		System.out.println(new Test().getStr(list));
	}
}

在this.contains(strList,sub))   返回false之后即运行到sub = "";之后可以加一句 i+=  length； 


好吧  我想了想发现这样改是不对地  泪飘

有种数据结构叫trie。

总体思路可以了，不过可以优化一下：

public class MaxSub {
	private static String findMaxSub(List<String> strings) {
		String s = strings.get(0);
		int len = s.length();
		int i = 0;
		String maxSub = "";
		while (i < len - maxSub.length()) {
			for (int j = len; j >= i + maxSub.length(); j--) {
				String sub = s.substring(i, j);
				int p = 1;
				while (p < strings.size() && strings.get(p).contains(sub)) p++;
				if (p == strings.size()) {
					maxSub = sub;
					break;
				}
			}
			i++;
		}
		return maxSub;
	}
	
	public static void main(String[] args) {
		List<String> strings = new ArrayList<String>(Arrays.asList(new String[]{
				"abacdefaabc",
				"abacdefaabc",
				"abbfecdefsdbc"
		}));
		
		System.out.println(findMaxSub(strings));
	}
}

1. 外层循环（子串开头字符）正向扫描，如果剩下的字符数不足已找到的最长公串，就不用继续了
2. 内层循环（子串结尾字符）反向扫描，扫描到剩下的字符数不足已找到的最长公串，就可以跳回外层循环了。而且找到的第一个公串肯定是最长公串，可以直接跳回外层循环。

Longest common substring problem问题。
维基百科：http://en.wikipedia.org/wiki/Longest_common_substring_problem
用广义后缀树求解O(n+m)，其中n,m是字符串长度。
关于后缀树，这篇文章总结的相当好：http://blog.csdn.net/tsengyuen/article/details/4815921
=====================================
如果时间有限，直接暴力得了。。。
=====================================
楼主笔什么公司啊，出这么变态的题目？

说一下思路，先用两个字符串比较得出公子串列表，然后在用这个公子串列表跟第三个字符串进行比较，中间涌递归，这样应该会比较好点，我只是想到思路，电脑没在身边所以没试过，希望楼主用这个方法试试

我想这道题的目的肯定是考算法，不会是用传统的暴力吧。。

很简单哦，先找出 最短的，然后，每次截取一个最前面的，和一个最后面的，匹配合适

我的思路是先把前面二个字符串的字符序列取交集，然后判断字符是否是连续的，
从而得出一个交集，然后与第三个字符串做交集，最后取交集中字符串长度最长的那个。
随便想了下，不知道对不对。。。

有一种算法叫KMP算法