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

  }else{   
                        sub = "";   
                        break;   
                    }   

import java.nio.Buffer;
import java.nio.CharBuffer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * 求N个字符串中的最大公子串
 *思路：
 *	1、从N个字符串中找出最小的字符串
 *	2、分解出最小字符串最大公字符串列表：
 *	例如：abcde
 *	--------------------
 *	abcde
 *	abcd
 *	bcde
 *	abc
 *	bcd
 *	cde
 *	ab
 *	bc
 *	cd
 *	de
 *	----------------------
 *	3、分解出来的公子串从上到下去匹配其他的字符，都能匹配成功则是所要查找的最大公子串
 *	4、如果同时存在两个相等长度的公子串 则以最先发现的为最大
 *
 */
public class MaxPublicStr {

	
	class Combination {

		private CharBuffer a(char[] a, int[] tempNum, int m, int n, int startInd) {
			for (int i = 0; i < n; i++) {
				if (i >= startInd && i < (m + startInd)) {
					tempNum[i] = 1;

				} else {
					tempNum[i] = 0;
				}
			}
			return createResult(a, tempNum, m);
		}

		/**
		 * @param a:组合数组
		 * @param m:生成组合长度
		 * @return :所有连续的组合数组列表
		 */
		public List<CharBuffer> combinationsequence(char[] a, int m) {
			List<CharBuffer> list = new ArrayList<CharBuffer>();
			int n = a.length;
			// 生成辅助数组。首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。
			int[] tempNum = new int[n];
			for (int i = 0; i < tempNum.length; i++) {
				if (i + m > n) {
					break;
				}
				list.add(a(a, tempNum, m, n, i));
			}
			return list;
		}

		// 根据辅助数组和原始数组生成结果数组
		@SuppressWarnings("unchecked")
		public CharBuffer createResult(char[] a, int[] temp, int m) {
			CharBuffer bos = CharBuffer.allocate(m);
			for (int i = 0; i < a.length; i++) {
				if (temp[i] == 1) {
					bos.put(a[i]);
				}
			}
			return bos;
		}

	}

	public List<CharBuffer> combinationsequence(String str, int m) {
		char[] a = str.toCharArray();
		Combination c = new Combination();
		List<CharBuffer> list = c.combinationsequence(a, m);
		return list;
	}

	//字符串列表中的最短字符串
	public String minStr(List<String> strings) {
		return Collections.min(strings, new Comparator<String>() {
			public int compare(String str1, String str2) {
				if (str1.length() < str2.length())
					return -1;
				else if (str1.length() == str2.length())
					return 0;
				else if (str1.length() > str2.length())
					return 1;
				return 0;
			}

		});
	}

	//判断字符串列表中的每个字符串是否包含指定字符串，如果有一个不包含就返回false
	public boolean contains(List<String> strings, String str) {
		for (String s : strings) {
			if (!s.contains(str))
				return false;
		}
		return true;
	}

	public String maxSubString(List<String> strings) {
		String shortStr = minStr(strings);
		int i = shortStr.length();
		//i是1 而不是0 因为当只有一个字符串的时候就没最大可言
		while (i > 1) {
			List<CharBuffer> list = combinationsequence(shortStr, i);
			for (CharBuffer charBuffer : list) {
				Buffer tempstr = charBuffer.rewind();
				if (contains(strings, tempstr.toString())) {
					return tempstr.toString();
				}
			}
			i--;
		}
		return null;
	}

	public static void main(String[] args) {
		MaxPublicStr max = new MaxPublicStr();
		ArrayList<String> strings = new ArrayList<String>(Arrays.asList("ababcdghy", "abcdeftdsfgsdg", "abcdefsdf"));
		String publicStr = max.maxSubString(strings);
		System.out.println(publicStr);

	}
}

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

		list.add("1a22b333x4444");
		list.add("11e222f3333d44444");
		list.add("111y2222u33333i444444");

public class Test2 {
	public String getSub(List<String> strs)
	{
		String sub 	 = "";
		String first = strs.get(0);
		int    len   = 0;
		for(int i=0;i<first.length();i++)
		{
			for(int j=i+1;j<first.length()+1;j++)
			{
				String falseSub = first.substring(i,j);
				boolean flag = true;
				for(int k=1;k<strs.size();k++)
				{
					if(!strs.get(k).contains(falseSub))
					{
						flag = false;
						break;
					}	
				}	
				if(flag && falseSub.length() > len)
				{
					len = falseSub.length();
					sub = falseSub;
				}	
			}	
		}
		
		return sub;
	}

	public static void main(String[] args) {
		List<String> list =new ArrayList<String>();
		list.add("4444x1a22b333x");
		list.add("d44444d11e222f3333");
		list.add("444444i111y2222u33333i");
		System.out.println(new Test2().getSub(list));
	}

}

String findLongestCommon(String[] strings){
    return findLongestCommon(strings,0,strings.length - 1);
}
String findLongestCommon(String[] strings,int start,int end){
    if(start < end){
        int mid = start + (end - start)/2;
        String longest1 = findLongestCommon(strings,start,mid);
        String longest2 = findLongestCommon(strings,mid+1,end);
        return findLongestCommon(longest1,longest2);
    }
    return strings[start];
}
String findLongestCommon(String a, String b){
    int maxLength = 0;
    String result = "";
    if(a.length() <= b.length()){
        for(int i=0; i<a.length(); i++){
            for(int j=i+1; j<a.length(); j++){
                String tmp = a.substring(i,j);
                if(b.indexOf(tmp) > -1){
                    if(tmp.length() > maxLength){
                        result = tmp;
                    }
                }
            }
        }
        return result;
    }
    return findLongestCommon(b,a);
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 求N个字符串中的最大公子串 思路：先找出字符串中最短的那个字符串,然后依次取出最短字符串中的每个字符与其余字符串进行比较。
 */
public class ShortString {
	// 定义字符串的比较器（根据长度比较）
	private class LengthComparator implements Comparator<String> {
		@Override
		public int compare(String str1, String str2) {
			if (str1.length() < str2.length())
				return -1;
			else if (str1.length() == str2.length())
				return 0;
			else if (str1.length() > str2.length())
				return 1;
			return 0;
		}
	}

	// 字符串列表中的最短字符串
	public String minStr(Collection<String> strings) {
		return Collections.min(strings, new LengthComparator());
	}

	// 判断字符串列表中的每个字符串是否包含指定字符串，如果有一个不包含就返回false
	public boolean contains(ArrayList<String> strings, String str) {
		for (String s : strings) {
			if (!s.contains(str))
				return false;
		}
		return true;
	}

	// 最短公共字符串
	public String maxSubString(ArrayList<String> strings) {
		String maxStr = "";// 最长公子串
		String tempStr = "";// 临时变量
		String minStr = minStr(strings);// 所有字符串中的最短字符串
		/**
		 * 思路：
		 * 1.先获得所有字符串中的最短的字符串
		 * 2.然后截取最短字符串(从长到短)，例如abcd，截取顺序abcd,abc,ab,a,bcd,bc,b,cd,c,d
		 * 3.将截取后的最短字符串与列表中的所有字符串比较
		 */
		for (int i = 0; i < minStr.length(); i++) {
			//如果最所剩字符数小于最长公子串长度，就直接进入跳出循环。
			//	例如：minStr ="abcd",maxStr="ab";那么就没有必要再遍历cd及cd的子串了
			if (maxStr.length() < minStr.length() - i) {
				for (int j = minStr.length(); j >= i; j--) {
					tempStr = minStr.substring(i, j);
					//如果截取的临时字符串长度 <= 最长公子串的长度，就没有必要再执行循环了，因为接下来的循环只能使临时字符串越来越短
					if (tempStr.length() <= maxStr.length())
						break;//结束内循环，跳到外循环
					if (contains(strings, tempStr)) {
						if (tempStr.length() > maxStr.length()) {
							maxStr = tempStr;
						}
					}
				}
			}else 
				break;
		}
		return maxStr;
	}

	public static void main(String[] args) {
		ArrayList<String> strings = new ArrayList<String>(Arrays.asList(
				"abdfdfabf", "abcabdeftdsfgsdg","abdcdefsdf"));
		ShortString ss = new ShortString();
		System.out.println("字符串列表：" + strings);
		System.out.println("最短字符串：" + ss.minStr(strings));
		System.out.println("最长公子串：" + ss.maxSubString(strings));
	}
}