【POJ3080】Blue Jeans

2023-10-20 09:50

文章标签 blue poj3080 jeans

本文主要是介绍【POJ3080】Blue Jeans，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题我们发现每个串的长度只有60

所以对于第一个串（或者选一个你喜欢的）枚举子串分别与其他串KMP匹配

注意长度相等时字典序最小&&长度<3时 no significant commonalities

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 const int len=60;
 5 int Q,n,tmplen,lenth,pre[65],m[65];
 6 char s[12][65],ans[65],tmp[65];
 7 int dic(){
 8     if (tmplen!=lenth) return 0;
 9     for (int i=1;i<=tmplen;i++){
10         if (tmp[i]<ans[i]) return 1;
11         if (tmp[i]>ans[i]) return 0;
12     }
13     return 0;
14 }
15 void KMP(int l,int r){
16     int p=l,q=1;
17     while (p<=r){
18         tmp[q]=s[1][p];
19         p++;q++;
20     }
21     tmplen=r-l+1;
22     pre[1]=0;
23     for (int i=2;i<=tmplen;i++){
24         int j=pre[i-1];
25         while (j&&tmp[j+1]!=tmp[i]) j=pre[j];
26         if (tmp[j+1]==tmp[i]) j++;
27         pre[i]=j;        
28     }
29     int k=1,judge;
30     while (k<n){
31         k++;judge=m[1]=0;
32         for (int i=1;i<=len;i++){
33             int j=m[i-1];
34             while (j&&tmp[j+1]!=s[k][i]) j=pre[j];
35             if (tmp[j+1]==s[k][i]) j++;
36             m[i]=j;
37             if (j==tmplen) {
38                 judge=1;break;
39             }
40         }
41         if (!judge) return;
42     }
43     if (lenth<tmplen||dic()){
44         int p=l,q=1;
45         for (int i=1;i<=tmplen;i++)
46             ans[i]=tmp[i];
47         lenth=tmplen;
48     }
49 }
50 int main(){
51     scanf("%d",&Q);
52     while (Q--){
53         memset(pre,0,sizeof(pre)); 
54         lenth=0; 
55         scanf("%d",&n);
56         for (int i=1;i<=n;i++)
57             scanf("%s",s[i]+1);
58         for (int i=1;i<=len;i++){
59             for (int j=i;j<=len;j++) KMP(i,j);
60         }
61         if (lenth<3) 
62             printf("no significant commonalities");
63         else 
64             for (int i=1;i<=lenth;i++){
65                 printf("%c",ans[i]);
66             }
67         printf("\n");
68     }
69     return 0;
70 }