【poj 3080】Blue Jeans（字符串--KMP+暴力枚举+剪枝）

野性酷女 2021-12-17 07:21 202阅读 0赞

**题意：**求n个串的字典序最小的最长公共子串。

**解法：**枚举第一个串的子串，与剩下的n-1个串KMP匹配，判断是否有这样的公共子串。从大长度开始枚举，找到了就break挺快的。而且KMP的作用就是匹配子串，近乎O(n)的速度，很快。

P.S.对于字符串要仔细！！！

1 #include<cstdio>
     2 #include<cstdlib>
     3 #include<cstring>
     4 #include<iostream>
     5 using namespace std;
     6 
     7 const int L=60;
     8 int n;
     9 int next[65],nextt[65];
    10 char s[12][65],ss[65],str[65];
    11 
    12 bool kmp(int x,int l,int r)
    13 {
    14     /*for (int i=1;i<=L;i++)
    15     {
    16       if (!next[i]) nextt[i]=l-1;
    17       else nextt[i]=next[i];
    18     }WA!!*/
    19     for (int i=l;i<=r;i++) ss[i-l+1]=s[1][i];
    20     memset(next,0,sizeof(next));
    21     int p=0;
    22     next[1]=0;
    23     for (int i=2;i<=r-l+1;i++)
    24     {
    25       while (ss[i]!=ss[p+1] && p) p=next[p];
    26       if (ss[i]==ss[p+1]) p++;
    27       next[i]=p;
    28     }
    29     p=0;
    30     for (int i=1;i<=L;i++)
    31     {
    32       while (s[x][i]!=ss[p+1] && p) p=next[p];
    33       if (s[x][i]==ss[p+1]) p++;
    34       if (p==r-l+1) return true;
    35     }
    36     return false;
    37 }
    38 bool check(int l,int r)
    39 {
    40     for (int i=2;i<=n;i++)
    41       if (!kmp(i,l,r)) return false;//O(n*n)匹配
    42     return true;
    43 }
    44 int main()
    45 {
    46     int T;
    47     scanf("%d",&T);
    48     while (T--)
    49     {
    50       scanf("%d",&n);
    51       for (int i=1;i<=n;i++) scanf("%s",s[i]+1);
    52       bool ok=false;
    53       for (int len=L;len>=3;len--)
    54       {
    55         for (int i=1;i+len-1<=L;i++)
    56         {
    57           if (!check(i,i+len-1)) continue;
    58           memset(ss,'\0',sizeof(ss));//
    59           for (int j=i;j<=i+len-1;j++) ss[j-i]=s[1][j];
    60           if (!ok||(ok && strcmp(ss,str)<0)) strcpy(str,ss);
    61           ok=true;
    62         }
    63         if (ok) break;
    64       }
    65       if (!ok) printf("no significant commonalities\n");
    66       else printf("%s\n",str);
    67     }
    68     return 0;
    69 }

转载于:https://www.cnblogs.com/konjak/p/6075802.html