xindoo is
always here

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 » light oj 1258 – Making Huge Palindromes(KMP)
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏