求N个字符串中的最大公子串
今天在网上看到有一道算法题目：
求N个字符串中的最大公子串
http://www.iteye.com/topic/1118325
刚好闲着，做之。
先说一下思路：
1、从N个字符串中找出最小的字符串
2、分解出最小字符串最大公字符串列表：
例如：abcde
--------------------
abcde
abcd
bcde
abc
bcd
cde
ab
bc
cd
de
----------------------
3、分解出来的公子串从上到下去匹配其他的字符，都能匹配成功则是所要查找的最大公子串
4、如果同时存在两个相等长度的公子串 则以最先发现的为最大
说完上代码：
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;}});}//判断字符串列表中的每个字符串是否包含指定字符串，如果有一个不包含就返回falsepublic 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);}}