题意：
给出一堆字符串，设X为一个字符串，其本身或者其反转传在每个字符串中均出现。问x的最长长度。
解法：
由于数据小，100个字符串，最大长度为100，我就用了二分+暴力枚举验证。。
二分字符串长度，然后枚举其中一个字符串的起始位置s，验证以s为起始，长度为len的字符串（或其反转串）是否在所有字符串中都出现（这步复杂度o(n3))
加上二分的复杂度，总复杂度为o(n
3logn)
正解应该是用后缀数组+二分。将所有原串和原串的反串连接起来计算后缀数组，二分子串长度，然后用height数组分类来验证。。复杂度o(n
2logn)
代码：
1
# include <cstdio>
2# include <cstring>
3using namespace std;
4char str[101][105];
5int n;
6void strreverse(char *str)
7
{
8
int len=strlen(str);
9 for(int i=0;i<len/2;i++)
10
{
11 char tmp=str[i];
12 str[i]=str[len-1-i];
13 str[len-1-i]=tmp;
14
}
15
}
16bool chk(int len,int pos)
17{
18 for(int s=0;s+len<=strlen(str[pos]);s++)
19 {
20 char tmp=str[pos][s+len];
21 bool flag=true;
22 str[pos][s+len]='\0';
23 for(int j=0;j<n;j++)
24 {
25 if(strstr(str[j],str[pos]+s)) continue;
26 else
27 {
28 strreverse(str[pos]+s);
29 char *p=strstr(str[j],str[pos]+s);
30 strreverse(str[pos]+s);
31 if(!p)
32 {
33 flag=false;
34 break;
35 }
36 }
37 }
38 str[pos][s+len]=tmp;
39 if(flag) return true;
40
41 }
42 return false;
43}
44int main()
45{
46 int test;
47 scanf("%d",&test);
48 while(test--)
49 {
50 int s=0,e=0xfffffff,pos;
51 scanf("%d",&n);
52 for(int i=0;i<n;i++)
53 {
54 scanf("%s",str[i]);
55 if(strlen(str[i])<e) e=strlen(str[i]),pos=i;
56 }
57 while(s<=e)
58 {
59 int mid=(s+e)>>1;
60 if(chk(mid,pos)) s=mid+1;
61 else e=mid-1;
62 }
63 printf("%d\n",s-1);
64 }
65 return 0;
66}
67
68