Problem Description
You are given a number of case-sensitive strings of alphabetic characters, find the largest string X, such that either X, or its inverse can be found as a substring of any of the given strings.
Input
The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer n (1 <= n <= 100), the number of given strings, followed by n lines, each representing one string of minimum length 1 and maximum length 100. There is no extra white space before and after a string.
Output
There should be one line per test case containing the length of the largest string found.
Sample Input
2
3
ABCD
BCDFF
BRCD
2
rose
orchid
Sample Output
2
2
在这总结一下n个字符串找公共子串的套路：
以最短的子串开始 .
1，先截取1个字符，然后到其余的n-1个字符去比较，发现区域的n-1个字符有包含这个字符的，则记录下来，为1个公共字符串，长度为1的子串。如题目中的ABDC，先截取A，然后跟后面2个字符串匹配，发现都没有A，则继续取B比较，发现都有B，则B保存下来。
2，在第一步的基础上往后再截取1个字符（如果第一步存在1个公共子串，则把第二部截取的字符拼接到第一步的子串后面），然后继续在n-1个字符串中比较，匹配成功了.取C加上第一步的B，构成BC。然后匹配其他2个字符串，发现第三个字符串没有BC，所以BC不可以，放弃，只能取B，公共子串长度仍为1。（注意,BC不可以，不代表C不可以）。
继续做第一步，发现C可以，再发现D也可以，所以更新为CD。
注意：
如果A没有，则以A为前缀的字符串都没有，所以就可以考虑把以A为开头的子串都放弃掉，转向比较B。
按照这个思路，自己写了一个java版的复杂度为 o（n）
package AA; public class my { static String sArray[] = { "ABCD", "BCDFF","CDFFy" }; public static boolean isSubString(String s) { boolean flag = true; for (String a : sArray) { if (a.indexOf(s) == -1 && a.indexOf(inverse(s)) == -1) { flag = false; break; } } return flag; } public static String inverse(String s) { String t = ""; for (char a : s.toCharArray()) t = a + t; return t; } public static void main(String argc[]) { String f=""; int i=0,j=1,length=0; boolean flag=true; String sub=""; while(true) { if(i>3)break; flag=true; String t = sArray[0]; String sub1 = t.substring(i,i+j); sub = sub+sub1; if( isSubString(sub)==false) { flag=false; } if(flag == true) { i++; f=sub; } else if(flag ==false) { sub=""; i++; } } System.out.println(f.length()); } }上面的代码从目标串开始检测，我把它称为 “ 头暴力“ ，缺点就是 必须把整个目标串遍历完才能保证找最长子串
下面这段代码我把它称为“尾暴力”，顾名思义，就是从目标串的尾部开始暴力， 优点：可以保证最先找到的公共子串既为最长的公共子串 package AA; //公共子串问题，暴力破解注意剪枝 public class Test3_2 { static String sArray[] = { "rose", "orchid" }; public static boolean isSubString(String s) { boolean flag = true; for (String a : sArray) { if (a.indexOf(s) == -1 && a.indexOf(inverse(s)) == -1) { flag = false; break; } } return flag; } public static String inverse(String s) { String t = ""; for (char a : s.toCharArray()) t = a + t; return t; } /** * @param args */ public static void main(String[] args) { int len=sArray[0].length(); String t=sArray[0]; int maxlen=0; for(int k=len;k>=1;k--){ //k不断截取字符串 长度为 4 3 2 1 当4的时候 做1次 当3的时候 做2次 当2的时候做3次 当1的时候，做四次 //从长到断，如果碰到了，就不再继续，跟我的那个算法刚好是反过来 boolean f=true; for(int i=0;i<=len-k;i++){ //i? int j=i+k; //j? System.out.println(t.substring(i,j)); if(isSubString(t.substring(i,j))&&j-1+1>maxlen){ maxlen=k; f=false; break;//退出内循环达到有效的剪枝效果 } } if(!f)break;//退出外循环达到有效的剪枝效果 } System.out.println(maxlen); } }
动态规划：
以一个m【i】【j】来表示当前 第i个字符到第j个字符的匹配情况，如果第i个字符到第j个字符是匹配的，既第i个字符到第j个字符能在其他串中找到相同的子串，则把m【i】【j】设为true m【i】【j】为true的条件是 m【i】【j-1】==true && m【j】【j】==true && 第j个字符能匹配
package AA; //公共子串问题，暴力破解注意剪枝 public class Test3_2 { static String sArray[] = { "rose", "orchid" }; public static boolean isSubString(String s) { boolean flag = true; for (String a : sArray) { if (a.indexOf(s) == -1 && a.indexOf(inverse(s)) == -1) { flag = false; break; } } return flag; } public static String inverse(String s) { String t = ""; for (char a : s.toCharArray()) t = a + t; return t; } /** * @param args */ public static void main(String[] args) { int len=sArray[0].length(); String t=sArray[0]; int maxlen=0; for(int k=len;k>=1;k--){ //k不断截取字符串 长度为 4 3 2 1 当4的时候 做1次 当3的时候 做2次 当2的时候做3次 当1的时候，做四次 //从长到断，如果碰到了，就不再继续，跟我的那个算法刚好是反过来 boolean f=true; for(int i=0;i<=len-k;i++){ //i? int j=i+k; //j? System.out.println(t.substring(i,j)); if(isSubString(t.substring(i,j))&&j-1+1>maxlen){ maxlen=k; f=false; break;//退出内循环达到有效的剪枝效果 } } if(!f)break;//退出外循环达到有效的剪枝效果 } System.out.println(maxlen); } }
