Posted on 2008-09-02 16:28
Hero 閱讀(107)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //3080 Accepted 332K 0MS G++ 1415B PKU
2
3 //暴力枚舉
4
5 #include <stdio.h>
6 #include <string.h>
7 #include <stdlib.h>
8
9 char data[15][70] ;
10 char sub[70] ;
11
12 char out[10000][70] ;
13 int ctout ;
14
15 int innum ;
16 int inn ;
17
18 void input()
19 {
20 scanf( "%d", &inn ) ;
21 for( int i=1; i<=inn; i++ )
22 {
23 scanf( "%s", data[i] ) ;
24 //printf( "%s\n", data[i] ) ;
25 }
26 }
27
28 int cmp( const void *a, const void *b )
29 {
30 return strcmp( (char *)a, (char *)b ) ;
31 }
32
33 bool test()
34 {
35 char *psub ;
36 for( int i=2; i<=inn; i++ )
37 {
38 psub = strstr( data[i], sub ) ;
39 if( NULL == psub ) return false ;
40 }
41
42 return true ;
43 }
44
45 void process()
46 {
47 int len = 60 ; ctout = 0 ; bool hasone = false ;
48 for( int clen=len; clen>=3; clen-- )
49 {
50 hasone = false ;
51
52 for( int sn=0; sn+clen<=len; sn++ )
53 {
54 int sublen = 0 ;
55 for( int i=sn; i<sn+clen; i++ ) sub[sublen++] = data[1][i] ;
56 sub[sublen] = '\0' ;//枚舉子串sub
57
58 if( false == test() ) continue ;
59 else
60 {
61 hasone = true ;
62 strcpy( out[ctout++], sub ) ;
63 }
64 }
65
66 if( hasone ) break ;
67 }
68
69 if( false == hasone )
70 {
71 printf( "no significant commonalities\n" ) ;
72 }
73 else
74 {
75 qsort( out, ctout, sizeof(out[0]), cmp ) ;
76 printf( "%s\n", out[0] ) ;
77 }
78 }
79
80
81 int main()
82 {
83 //freopen( "in.txt", "r", stdin ) ;
84
85 while( scanf( "%d", &innum ) != EOF )
86 {
87 for( int ct=1; ct<=innum; ct++ )
88 {
89 input() ;
90
91 process() ;
92
93 //output() ;
94 }
95 }
96
97 return 0 ;
98 }