更好的方法：后綴數(shù)組 + 棧掃描
我的程序還可以在優(yōu)化下：記錄當(dāng)前的長度，不去搜索比它小的子串
1
#include <cstdio>
2#include <cstring>
3
4const int STRNUM = 10 ;
5const int SIZE = 62 ;
6
7char str[STRNUM][SIZE] ;
8int N ;
9
10int next[STRNUM][SIZE] ;
11
12bool FindSubstr( const int& k, const char* des )
13
{
14
int i = 0 , j = 0 , srcLen = strlen(str[k]) , desLen = strlen(des) ;
15
16 while ( i < srcLen && j < desLen )
17
{
18 if ( j == -1 || str[k][i] == des[j] )
19 {
20 i++ ;
21 j++ ;
22
}
23 else j = next[k][j] ;
24 }
25
26 if ( j >= desLen )
27 return true ;
28 else
29 return false ;
30
}
31
32void GetNext()
33{
34
35 for ( int i = 0 ; i < N ; ++i )
36 {
37 int j = 0 , k = -1 ;
38
39 next[i][0] = -1 ;
40
41 while ( j < (int)strlen(str[i]) )
42 {
43 if ( k == -1 || str[i][j] == str[i][k] )
44 {
45 j++ ;
46 k++ ;
47 next[i][j] = k ;
48 }
49 else
50 k = next[i][k] ;
51 }
52 }
53}
54
55void Solve()
56{
57 int i , j , k ;
58
59 int len = (int)strlen(str[0]) ;
60 char temp[SIZE] ;
61
62 bool ok = false ;
63 char result[SIZE] ;
64 int rLen ;
65
66 GetNext() ;
67
68 for ( i = 0 ; i < len - 2 ; ++i )
69 {
70 for ( j = i , k = 0 ; j < len ; ++j , ++k )
71 temp[k] = str[0][j] ;
72
73 for ( j = k ; j > 2 ; --j )
74 {
75 temp[j] = '\0' ;
76
77 for ( k = 1 ; k < N ; ++k )
78 {
79 if ( !FindSubstr( k, temp ) )
80 {
81 break ;
82 }
83 }
84
85 if ( k == N )
86 {
87 if ( ok )
88 {
89 int tLen = (int)strlen(temp) ;
90 if ( tLen > rLen || (tLen == rLen && strcmp(temp, result) < 0) )
91 {
92 rLen = tLen ;
93 strcpy( result, temp ) ;
94 }
95 }
96 else
97 {
98 ok = true ;
99 strcpy( result, temp ) ;
100 rLen = (int)strlen(result) ;
101 }
102 }
103
104 }
105 }
106
107 if ( ok )
108 {
109 printf("%s\n", result) ;
110 }
111 else {
112 printf("no significant commonalities\n") ;
113 }
114
115}
116
117void Input()
118{
119 int i , n , m ;
120
121 scanf("%d", &n) ;
122
123 while ( n-- )
124 {
125 scanf("%d", &m) ;
126
127 N = m ;
128
129 getchar() ;
130
131 for ( i = 0 ; i < m ; ++i )
132 {
133 gets(str[i]) ;
134 }
135
136 Solve() ;
137 }
138
139}
140
141int main()
142{
143// freopen("1.txt", "r", stdin) ;
144
145 Input() ;
146
147 return 0 ;
148}