codeforces 443 B. Kolya and Tandem Repeat 解题报告

题目链接：http://codeforces.com/contest/443/problem/B

题目意思：给出一个只有小写字母的字符串s（假设长度为len），在其后可以添加 k 个长度的字符，形成一个长度为len+k的新串 s'。问在 s' 中，可以形成的最长tandem repeat 是多长。tandem repeat 的定义是：si = si+n （1 <= i <= n; 2*n <= k+len）

注意，这个tandem repeat 是相邻的！！也就是对于abcwerabc?? （??，表示可以添加的长度为k = 2），如果?? 填入we，并不代表之前的abcwe（a下标：0）== abcwe（a下标：6），因为中间多了个r ！答案其实是4。只能将?? 变为 bc，这样的tandem repeat 的长度为2*2 = 4(两个bc相等)

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;

 const int maxn =  + ;

 char str[maxn];

 int main()

 {

     int k;

     while (scanf("%s%d", str, &k) != EOF)

     {

         int len = strlen(str);

         if (len <= k)

             printf("%d\n", (len+k)& ? len+k-: len+k);

         else

         {

             int ans = ;

             for (int i = ; i < len; i++)  // 枚举原串s的每个位置

             {

                 for (int j = i+; *j-i <= len+k; j++)  // 2*j-i <= len+k：控制住si+n不大于新串s'的长度

                 {

                     bool ok = true;

                     for (int l = ; l < j-i && l+j < len; l++)  // 枚举间隙，j-i代表间隙，也就是题目中si = si+n中的n

                     {

                         if (str[i+l] != str[j+l])

                         {

                             ok = false;

                             break;

                         }

                     }

                     if (!ok)

                         continue;

                     ans = max(ans, *(j-i));

                 }

             }

             printf("%d\n", ans);

         }

     }

     return ;

 }

　　补充一点，对于l+j < len 这个条件是必不可少的！因为它保证比较的是原序列 s 的字符有 tandem repeat，这些字符是确定的。而对于后面添加的 k 个字符是不确定的，所以就不能单纯用str[i+l] = str[j+l] 来比较了。但由于有 2*j - i <= len+k，所以j 的值还是可以取的(一直ok = true)，它默认 k 个字符中任意填字符，可以使得s' 有 tandem repeat，2*(j-i）就是求出repeat的长度了。

巴特西

codeforces 443 B. Kolya and Tandem Repeat 解题报告

最新文章

热门文章