2013
11-09

# Substrings

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.

The first line of the input 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.

There should be one line per test case containing the length of the largest string found.

2
3
ABCD
BCDFF
BRCD
2
rose
orchid

2
2 

//* @author:alpc12
import java.math.*;
import java.io.*;
import java.util.*;

class Main {
public static void main(String[] args) throws Exception {
new Main().run();
}

private int n;

private void run() throws Exception {
Scanner cin = new Scanner(System.in);
int ntc = cin.nextInt(),i,j,k;
while(ntc-- != 0) {
n = cin.nextInt();
StringBuffer[] s = new StringBuffer[n];
for(i = 0; i < n; ++i) {
s[i] = new StringBuffer(cin.next());
}
int max = 0;
for(i = 0; i < s[0].length(); ++i) {
for(j = i+1; j <= s[0].length(); ++j) {
if(check(s,i,j)) {
max = Math.max(max,j-i);
}
}
}
System.out.println(max);
}
}

boolean check(StringBuffer s[], int x, int y) {
int i;
String pattern1 = s[0].toString().substring(x, y);
String pattern2 = "";
for(i = pattern1.length()-1; i >= 0; --i) {
pattern2 += pattern1.charAt(i);
}
for(i = 0; i < n; ++i) {
if(s[i].toString().indexOf(pattern1) == -1
&& s[i].toString().indexOf(pattern2) == -1) {
return false;
}
}
return true;
}
}

1. #include <cstdio>
#include <algorithm>

struct LWPair{
int l,w;
};

int main() {
//freopen("input.txt","r",stdin);
const int MAXSIZE=5000, MAXVAL=10000;
LWPair sticks[MAXSIZE];
int store[MAXSIZE];
int ncase, nstick, length,width, tmp, time, i,j;
if(scanf("%d",&ncase)!=1) return -1;
while(ncase– && scanf("%d",&nstick)==1) {
for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
for(time=-1,i=0;i<nstick;++i) {
tmp=sticks .w;
for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
if(j==time) { store[++time]=tmp; }
else { store[j+1]=tmp; }
}
printf("%dn",time+1);
}
return 0;
}

2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。