簡單的求最大子串問題，難點在於反向比較的也要算
[java]
package D0710;
/*
* 求子串問題
* 思路：
*1、 獲得每組測試數據中最短的字符串
*2、用最短的字符串的子串進行正相匹配和反向匹配
*3、得長度最大的子串即可
*
*/
import java.util.Scanner;
public class HDU1238 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t;
int n;
String[] str;// 保存接收輸入的字符串
String[] str2;// 保存str的反串
StringBuffer sb;
String s;// 保存每組測試數據中最短字符串
int len;// 最後得到的最大子串長度
t = sc.nextInt();
while (t-- > 0) {
n = sc.nextInt();
str = new String[n];
str2 = new String[n];
// 接收輸入
for (int i = 0; i < n; i++) {
str[i] = sc.next();
sb = new StringBuffer(str[i]);
str2[i] = sb.reverse().toString();
}
// 得最短字符串, str2中的最短字符串應當和str中一致
s = str[0];
for (int i = 0; i < n; i++) {
if (str[i].length() < s.length()) {
s = str[i];
str2[i] = s;
}
}
if (s.equals(str[0])) {
str[0] = str2[0] = s;
}
// 匹配,得最大子串長度
len = getLen(s, str, str2);
System.out.println(len);
}
}
private static int getLen(String s, String[] str, String[] str2) {
int l = str.length;
boolean flag = false;
int l2 = s.length();
String sub;// 子串
String rsub = "";// 最後的子串
int i, j, k;// 循環變量
for (i = 0; i < l2; i++) {
for (j = i + 1; j <= l2; j++) {
sub = s.substring(i, j);
// 正向匹配
for (k = 0; k < l; k++) {
if (str[k].contains(sub)) {
flag = true;
} else {
flag = false;
break;
}
}
if (flag) {
if (sub.length() > rsub.length())
rsub = sub;
}
// 反向匹配
for (k = 0; k < l; k++) {
if ( str2[k].contains(sub)) {
flag = true;
} else {
flag = false;
break;
}
}
if (flag) {
if (sub.length() > rsub.length())
rsub = sub;
}
}
}
//System.out.println(rsub);
return rsub.length();
}
}
作者：lhfight
