首页 > 代码库 > POJ 3080 - Blue Jeans

POJ 3080 - Blue Jeans

2024-08-13 14:28:37   211人阅读

题意：

　　求所有串的最长公共子串，若有多个输出字典序最小的

分析：

　　对第一个串的每一个后缀分别与剩下的所有串进行匹配，求得公共子串

　　对每一个公共子串，记录下最大值即可.

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 const int MAXN = 66; 6 int nxt[MAXN]; 7 void GetNxt(char p[], int m) 8 { 9     int j = 0, k = -1; 10     nxt[0] = -1;11     while(j < m)12     {13         if(k != -1 && p[j] != p[k]) k = nxt[k];14         else nxt[++j] = ++k;15     }16 }17 int KMP(char s[], int n, char p[], int m)18 {19     int res = 0;20     for (int i = 0, k = 0; i < n; i++)21     {22         while (k > 0 && p[k] != s[i]) k = nxt[k];23         if (p[k] == s[i]) k++;24         res = max(res, k);25         if (k == m) k = nxt[k];26     }27     return res;28 }29 char p[MAXN], s[20][MAXN];30 int n, t, len;31 int ans;32 char res[MAXN], T[MAXN];33 int main()34 {35     scanf("%d", &t);36     while (t--)37     {38         ans = 0;39         scanf("%d", &n);40         scanf("%s", p);41         len = strlen(p);42         for (int i = 1; i < n; i++) scanf("%s", s[i]);43         44         for (int i = 0; i < len; i++) // 枚举每一个后缀 45         {46             int tmp = 66;47             GetNxt(p+i, len-i);48             for (int j = 1; j < n; j++)49                 tmp = min(tmp, KMP(s[j], len, p+i, len-i)); // 公共匹配的长度 50             51             strncpy(T, p+i, tmp);52             T[tmp] = ‘\0‘;53             if (tmp > ans) //记录最大值 54             {55                 ans = tmp;56                 strcpy(res, T);57             }58             else if (tmp == ans && strcmp(res, T) > 0)59             {60                 strcpy(res, T);61             }62         }63         if (ans < 3) puts("no significant commonalities");64         else puts(res);65     }66 }

 

POJ 3080 - Blue Jeans


联系
我们