light oj 1258 - Making Huge Palindromes(KMP)

题目链接

题意：

     给你一个字符串，在字符串尾部加上一些字符，使这个字符串变成一个回文串（正反读都一样的字符串），求该回文串的最小长度。

思路：

     在light oj里这个题目是属于KMP分类的，但乍看好像不是kmp，因为只有一个字符串。要想的到一个回文串，把该字符串翻转接到原串后面必然是一个回文串，但并不一定是最短的。我们必须考虑怎么把两个串尽量融合在一起，这就要看翻转串的前段与原串的后段有多少是匹配的了，这里就用到了KMP算法。

代码：

      //2013-05-13-20.01
      #include <stdio.h>
      #include <string.h>
      const int maxn = 1000005;
      char a[maxn];
      char b[maxn];
      int f[maxn];
      void getfail()
      {
         int l = strlen(b);
          f[0] = 0;
          f[1] = 0;
         for (int i = 1; i < l; i++)
          {
             int j = f[i];
             while (j && b[i] != b[j])
                  j = f[j];
             if (b[i] == b[j])
                  f[i+1] = j+1;
             else
                  f[i+1] = 0;
          }
      }
      int getans()
      {
         int la = strlen(a);
         int lb = strlen(b);
         getfail();
         int j = 0;
         for (int i = 0; i < la; i++)
          {
             while (j && a[i] != b[j])
                  j = f[j];
             if (b[j] == a[i])
                  j++;
          }
         return la + lb - j;
      }
      int main()
      {
         int t;
         scanf("%d", &t);
         for (int i = 1; i <= t; i++)
          {
             scanf("%s", a);
             int l = strlen(a);
             for (int j = 0; j < l; j++)
              {
                  b[l-j-1] = a[j];
              }
              b[l] = '\0';
             printf("Case %d: %d\n", i, getans());
          }
         return 0;
      }
  
 

文章来源: xindoo.blog.csdn.net，作者：xindoo，版权归原作者所有，如需转载，请联系作者。

原文链接：xindoo.blog.csdn.net/article/details/8922278