POJ3080 Blue Jeans

　　蓝色牛仔裤？
　　中规中矩的字符串匹配唯一的陷阱就是同等长度的子串输出字典序最小的。。。。。
　　最烂的代码 ……没有之一……
  1 #include <cmath>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <cstdio>
  5 #include <iostream>
  6 #include <algorithm>
  7 #include <queue>
  8 
  9 using namespace std;
 10 
 11 char s[11][62];
 12 
 13 bool check(char *s1,char *s2,int st,int l)
 14 {
 15 
 16 
 17 
 18     int ls2 = strlen(s2);
 19 
 20     if(l > ls2)
 21         return false;
 22 
 23     /*printf("st1 = %d l = %d ls2 = %d :: ",st,l,ls2);
 24     for(int j = st; j < st+l; ++j)
 25         printf("%c",s1[j]);
 26     printf("
");*/
 27 
 28     int st2;
 29     int i;
 30 
 31 
 32     for(st2 = 0; st2 < ls2; ++st2)
 33     {
 34         /*printf("st2 = %d ls2 = %d:: ",st2,ls2);
 35         for(int j = st2; j < st2+l; ++j)
 36             printf("%c",s2[j]);
 37         printf("

");*/
 38         for(i = 0; i < l; ++i)
 39         {
 40             if(s1[i+st] != s2[i+st2])
 41                 break;
 42         }
 43         if(i == l)
 44             return true;
 45     }
 46     return false;
 47 }
 48 
 49 int stack[60];
 50 
 51 int main()
 52 {
 53     int T;
 54 
 55     int top;
 56     bool flag ;
 57     int i;
 58     int st,e,l,cl,k,n;
 59     cin>>T;
 60     while(T--)
 61     {
 62         top = 0;
 63         flag = false;
 64         cin>>n;
 65         for(i = 0; i < n; i++)
 66             cin>>s[i];
 67 
 68         for(l = strlen(s[0]),cl = l; l >= 3; --l)
 69         {
 70             for(st = 0; st <= cl-l; ++st)
 71             {
 72 
 73                 for(k = 1; k < n; ++k)
 74                 {
 75                     if(check(s[0],s[k],st,l) == false)
 76                     {
 77                         break;
 78                     }
 79                 }
 80                 if(k == n)
 81                 {
 82                    flag = true;
 83                     stack[top++] = st;
 84                 }
 85             }
 86             if(flag)
 87                 break;
 88         }
 89         if(l == 2)
 90             printf("no significant commonalities
");
 91         else
 92         {
 93             int j,Min = stack[0];
 94 
 95             for(i = 1;i < top; ++i)
 96             {
 97                 for(j = 0;j < l; ++j)
 98                 {
 99                     if(s[0][stack[i]+j] < s[0][Min+j])
100                     {
101                         Min = stack[i];
102                         break;
103                     }
104                 }
105             }
106 
107             for(i = Min,e = Min+l; i < e; ++i)
108             {
109                 printf("%c",s[0][i]);
110             }
111             printf("
");
112         }
113     }
114     return 0;
115 }
View Code