POJ 3080 Blue Jeans、POJ 3461 Oulipo—

POJ 3080 Blue Jeans、POJ 3461 Oulipo——KMP应用

阅读量：7086 次

发布时间：2019-06-28

本文共 2094 字，大约阅读时间需要 6 分钟。

题目：POJ3080

题意：对于输入的文本串，输出最长的公共子串，如果长度相同，输出字典序最小的。

这题数据量很小，用暴力也是16ms，用后缀数组可以到0ms，但我不会XD。

暴力：

1 #include
     
       2 #include
      
        3 using namespace std; 4 char str[15][65],ans[65]; 5 int main(){ 6     int T,n;  scanf("%d", &T); 7     while (T--){ 8         memset(ans,0,sizeof(ans)); 9         scanf("%d", &n);10         for (int i = 0; i < n; i++)  scanf("%s", str[i]);11 12         for (int i = 0; i < strlen(str[0]); i++)13             for (int j = i + 2; j < strlen(str[0]); j++){14                 char s[65];//子串15                 strncpy(s, str[0] + i, j - i + 1);///strncpy16                 s[j - i + 1] = '\0';17 18                 int flag = 1;19                 for (int k = 1; flag && k < n; k++)20                     if (strstr(str[k], s) == NULL)21                         flag = 0;22                 ///匹配成功,判长度和字典序23                 if (flag && (j - i + 1 > strlen(ans) || (j - i + 1 == strlen(ans)&&strcmp(ans, s)>0) ) )24                     strcpy(ans, s);25             }26 27         if (strlen(ans) < 3)  puts("no significant commonalities");28         else  puts(ans);29     }30     return 0;31 }

KMP：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 char str[15][65],ans[65]; 6 int next[65]; 7 //计算串str的next数组 8 void getnext(char *str){ 9     int len=strlen(str);10     int j=0,k=-1;11     next[0]=-1;12     while(j
        
         strlen(ans) || ( strlen(s)==strlen(ans)&&strcmp(s, ans)<0)))52                         strcpy(ans, s);53             }54 55         if(strlen(ans) < 3)   puts("no significant commonalities");56         else  puts(ans);57     }58     return 0;59 }

题目：POJ3461

题意：求第一个串在第二个串中出现的次数

1 //求第一个串在第二个串中出现的次数 2 #include
     
       3 #include
      
        4 #include
       
         5 using namespace std; 6 #define MAXN 1000050 7 char s[MAXN],t[MAXN]; 8 int next[MAXN]; 9 void getnext(char *str){10     int len=strlen(str);11     int j=0,k=-1;12     next[0]=-1;13     while(j