題意：
給出一堆字符串，設(shè)X為一個(gè)字符串，其本身或者其反轉(zhuǎn)傳在每個(gè)字符串中均出現(xiàn)。問(wèn)x的最長(zhǎng)長(zhǎng)度。
解法：
由于數(shù)據(jù)小，100個(gè)字符串，最大長(zhǎng)度為100，我就用了二分+暴力枚舉驗(yàn)證。。
二分字符串長(zhǎng)度，然后枚舉其中一個(gè)字符串的起始位置s，驗(yàn)證以s為起始，長(zhǎng)度為len的字符串（或其反轉(zhuǎn)串）是否在所有字符串中都出現(xiàn)（這步復(fù)雜度o(n3))
加上二分的復(fù)雜度，總復(fù)雜度為o(n
3logn)
正解應(yīng)該是用后綴數(shù)組+二分。將所有原串和原串的反串連接起來(lái)計(jì)算后綴數(shù)組，二分子串長(zhǎng)度，然后用height數(shù)組分類來(lái)驗(yàn)證。。復(fù)雜度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