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

典型的KMP算法

这个貌似挺不错，测试一下先……

首先，这个可以先排序，就算不排序的话，最好先求出长度最小的字符串，再和别的字符串比较
其次，因为这个是求最大公字串，所以从最长的公字串与其它的字符串比较，一旦有合适的，后面的就可以不用比了；
随便写了点小程序玩玩
public static void foo2(String[] strs){
long time=System.currentTimeMillis();
String first=strs[0];
int length=strs[0].length();
for(int i=1;i<strs.length;i++){
int leng=strs[i].length();
if(length>leng){
first=strs[i];
length=leng;
}
}

/*char[] ones=first.toCharArray();
char[] twos=second.toCharArray();
int two=twos.length;
int one=ones.length;*/
all:
for(int i=length;i>0;i--){
for(int j=0;j<=length-i;j++){
String str=first.substring(j,j+i);
for(int k=0;;){
if(k<strs.length){
if(strs[k].contains(str)){
k++;
}else{
break;
}
}else{
System.out.println(str);
System.out.println("耗时："+(System.currentTimeMillis()-time)+"ms");
break all;
}
}
}
}
}

。。。已故： "abcabc", "cabcfffffff"
看来至少两重循环是跑不掉的了

kmp算法

贴一段代码, 供大家批评, 都是基本的思路, 没有滑头

如果对于算法非常感兴趣, 可以去这个网站挑战一下:　http://projecteuler.net/

package com.tianxiaohui.art.question.arithmetic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *  问题来源:　http://www.iteye.com/topic/1118325
 *  面试题目：求N个字符串中的最大公子串，比如： 
 *  1、abcde 
 *  2、abefg 
 *  3、werabc 
 *  这三个字符串的最大公子串是ab 
 * @author Eric.Tian
 */
public class MaxSharedSubString {

	public static void main(String[] args) {
		
		ArrayList<String> strings = new ArrayList<String>(Arrays.asList("abcdefsdfababcghy", "abcdeftdsfabcdefsdf", "abcdefsdf", "abcdabcdefsdfdg", "abcdabcdefsdfdgabcdabcdefsdfdgabcdabcdefsdfdg"));
		//ArrayList<String> strings = new ArrayList<String>(Arrays.asList("abcabc", "cabcfffffff"));
		long start = System.currentTimeMillis();
		System.out.println(MaxSharedSubString.getMaxSharedSubString(strings));
		System.out.println("Cost: " + (System.currentTimeMillis() - start));
	}
	
	public static String getMaxSharedSubString(List<String> strs) {
		// 以最短字符串为基准去测试
		String shortestStr = MaxSharedSubString.getShortestStr(strs);
		
		String maxSharedSubStr = "";
		int j = 0;
		String tmpStr = "";
		// 最短字符串的每个字符开头的字符
		for (int i = 0; i < shortestStr.length(); i++) {
			// 从以这个字符开头的最长字符子串开始, 逐渐缩短, 但不能短于已经找到的最短串
			for (j = shortestStr.length(); j > i & (j - i) > maxSharedSubStr.length(); j--) {
				tmpStr = shortestStr.substring(i, j);
				// Check 一下是不是都含有这个子串
				if (MaxSharedSubString.ifAllHave(strs, tmpStr)) {
					maxSharedSubStr = tmpStr;
				}
			}
		}
		
		return maxSharedSubStr;
	}
	
	private static String getShortestStr(List<String> strs) {
		String tmpStr = strs.get(0);
		
		for (String str : strs) {
			if (str.length() > tmpStr.length()) {
				tmpStr = str;
			}
		}
		
		return tmpStr;
	}
	
	private static boolean ifAllHave(List<String> strs, String string) {
		for (String str : strs) {
			if (!str.contains(string)) {
				return false;
			}
		}
		
		return true;
	}
}

算法书上有，忘记了，大概叫longest common subsuquence。是关于动态规划的一个问题。

这不是LCS，这是后缀树组问题

说动态规划的兄弟，请分析你们的动态递归解。这貌似不是那么容易动态规划的！这里有个动态规划之最长公共子序列的例子，http://songzi0206.iteye.com/blog/1160277，比较之后发现，对于本帖的例子，第一个动态分析算式都不成立。

//如果剩余的字符数小于公子串长度，就没有必要再比较了 
                if(minStr.length()-i<maxStr.length()) 
                    break; 
tempStr = minStr.charAt(i)+"";

这个有问题吧:
1. 剩余字符数小于当前公子串长度，并不代表剩余的字符就没用了，如abcde（实际的最大公子串是bcde），当发现abc不匹配的时候，难道就要放弃？
2. 一次搜索失败后再次搜索时最小字符串的起始字符偏移不正确，如：发现abc不匹配时（假如这是第1次搜索即 i从0开始），i=2，重新搜索时i应该从1开始