51Nod－1088－最长回文子串

回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。
输入一个字符串Str，输出Str里最长回文子串的长度。
Input
输入Str（Str的长度 <= 1000)
Output
输出最长回文子串的长度L。
Input示例
daabaac
Output示例
5

这道题，如果用暴力解题，那么就是一道水题。

#include<stdio.h>
#include<string.h>

char s[1000];
int solve(char ch[])
{
    int n = (int)strlen(ch);
    for(int i=0;i<n/2;i++)
    {
        if(ch[i]!=ch[n-1-i])
            return 1;
    }
    return 0;
}
int main()
{
    char ch[1000];
    scanf("%s",s);
    int n = (int)strlen(s);
    int ans=0,max=0;
    for(int i=0;i<n;i++)
    {
        for(int j=n-1;j>=i;j--)
        {
            int k=0;
            for(int o=i;o<=j;o++)
            {
                ch[k++]=s[o];
            }
            ch[k]='\0';
            if(solve(ch)==0)
            {
                ans=j-i;
                if(ans>max)
                    max=ans;
            }
        }
    }
    printf("%d\n",max+1);
    return 0;
}

但是这个方法的复杂度太高，如果字串再长些，绝对挂，考虑到拓展性，所以，一定有更好的算法，代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX(a,b) ((a>b)?(a):(b))
int f[2005];
char str[2005];

int main()
{
    int i, j, k, max = 0, o, r, l;
    scanf("%s", str);
    l = (int)strlen(str);
    //扩充为原来两倍长，中间补*号
    for(i = l - 1; i >= 0; i--)
    {
        str[2 * i] = str[i];
        str[2 * i - 1] = '*';
    }

    for(o = 0, r = 0, i = 1; i <=2 * (l - 1); i++)
    {
        if(i > (o + r))
        {
            j = i - 1;
            k = i + 1;
        }
        else if (f[2 * o - i] >= o + r - i)
        {
            k = o + r + 1;
            j = 2 * i - k;
        }
        else
        {
            f[i] = f[2 * o - i];
            continue;
        }
        while (j >= 0 && k <= 2 * (l - 1) && str[j] == str[k])
        {
            j--;
            k++;
        }
        f[i] = --k - i;
        if(k >= o + r)
        {
            r = k - i;
            o = i;
            max = MAX((r + o % 2) / 2 * 2 - (o % 2) + 1, max);
        }
    }

    printf("%d", max);
    return 0;
}