poj 3080 -- Blue Jeans

  1 /*======================================================================
  2  *           Author :   kevin
  3  *         Filename :   BlueJeans.cpp
  4  *       Creat time :   2014-07-20 09:12
  5  *      Description :
  6 ========================================================================*/
  7 #include <iostream>
  8 #include <algorithm>
  9 #include <cstdio>
 10 #include <cstring>
 11 #include <queue>
 12 #include <cmath>
 13 #define clr(a,b) memset(a,b,sizeof(a))
 14 #define M 100
 15 using namespace std;
 16 
 17 char str[15][M];
 18 struct Node{
 19     char str[M];
 20 }node[15];
 21 int n;
 22 
 23 void GetNext(char str[],int next[])
 24 {
 25     int j = 0, k = -1;
 26     next[0] = -1;
 27     int len = strlen(str);
 28     while(j < len){
 29         if(k == -1 || str[j] == str[k]){
 30             j++;
 31             k++;
 32             next[j] = k;
 33         }
 34         else k = next[k];
 35     }
 36 }
 37 
 38 bool KMP(char str[],char t[])
 39 {
 40     int len1 = strlen(t);
 41     int len2 = strlen(str);
 42     int next[M],i = 0,j = 0;
 43     clr(next,0);
 44     GetNext(str,next);
 45     while(i < len1 && j < len2){
 46         if(j == -1 || str[j] == t[i]){
 47             i++;
 48             j++;
 49         }
 50         else j = next[j];
 51     }
 52     if(j >= len2) return true;
 53     return false;
 54 }
 55 
 56 bool cmp(struct Node a,struct Node b)
 57 {
 58     return strcmp(a.str,b.str)<0;
 59 }
 60 int main(int argc,char *argv[])
 61 {
 62     int cas;
 63     scanf("%d",&cas);
 64     while(cas--){
 65         scanf("%d",&n);
 66         for(int i = 0; i < n; i++){
 67             getchar();
 68             scanf("%s",str[i]);
 69         }
 70         char s[M];
 71         int l,flag = 0;
 72         int len = strlen(str[0]);
 73         int num = 0;
 74         for(int i = len; i >= 1; i--){
 75             for(int j = 0; j <= len-i; j++){
 76                 int cnt = 0;
 77                 for(int k = j; cnt < i; k++){
 78                     s[cnt++] = str[0][k];
 79                 }
 80                 s[cnt] = ‘\0‘;
 81                 for(l = 1; l < n; l++){
 82                     if(!KMP(s,str[l])){
 83                         break;
 84                     }
 85                 }
 86                 if(l == n){
 87                     flag = 1;
 88                     strcpy(node[num++].str,s);
 89                 }
 90             }
 91             if(flag) break;
 92         }
 93         int len1 = strlen(s);
 94         if(len1 < 3){
 95             printf("no significant commonalities\n");
 96         }
 97         else{
 98             sort(node,node+num,cmp);
 99             printf("%s\n",node[0].str);
100         }
101     }
102     return 0;
103 }