[ACdream]女神教你字符串——导字符串

Problem Description

正如大家知道的,女神喜欢字符串,而在字符串中,女神最喜欢回文字符串,但是不是所有的字符串都是回文字符串,但是有一些字符串可以进行“求导”来变成回文字符串。

字符串中只包含小写字母。
求导过程如下,C++:

string dif(const string x)
{
    if(x.length()<=1)
        return "";
    string res="";
    for(int i=1;i<x.length();++i)
        res+=abs(x[i]-x[i-1])+'a';
    return res;
}

C:

void dif(char*x,char*res)//注意有可能会溢出
{
    if(x[0]==0||x[1]==0)
    {
        res[0]=0;
        return;
    }
    int len=1;
    for(int i=1;x[i];++i,++len)
        res[i-1]=abs(x[i]-x[i-1])+'a';
    res[len-1]=0;
}

例如"aa"的导字符串是“a",”aab“的导字符串是"ab","aacfwssg"的导字符串是"acdream"。

那么给定一个字符串,请判断在它各阶导字符串中,最长的回文串是多长?

二阶导字符串即为导字符串的导字符串。

n阶导字符串即为n-1阶导数的导字符串。

Input

多组数据,每组数据包括一个字符串s(1<=|s|<=1000)

Output

对于每组数据,输出一个整数

Sample Input

abcd
abcba
acdream

Sample Output

3
5
3

Hint

样例一,求一次导字符串后为”aaa“,最长回文子串就是本身,所以长度为3

样例二,本身就是回文串,因此,输出本身长度即可

样例三,acdream->cbonem->bnbji->mmib->aeh->ed->b

最长回文串长度分别为1,1,3,2,1,1,1,因此输出3

解题思路:

    核心就是求最大回文串,但是又不是直接求的,是要求不停的求异后的最大回文串,这题就是由于数据不大,直接从本身到求异后,调用Manacher算法就可以找到最大回文串,然后求最大的就可以了!

AC代码:

#include<iostream>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
char ss[2005],s[2005],res[3005];
int p[2005];

void dif(char *s,char *res)
{
    if(s[0]==0||s[1]==0)
    {
        res[0]=0;
        return;
    }
    int len=1;
    for(int i=1;s[i];++i,++len)
        res[i-1]=abs(s[i]-s[i-1])+'a';
    res[len-1]=0;
}
int Manacher(char *s)
{
    int len = strlen(s), maxp = 0, ans = 0;
    for(int i = len; i >= 0; i--)
    {
        s[i * 2 + 2] = s[i];
        s[i * 2 + 1] = '#';
    }
    s[0] = '*';
    for(int i = 2; i < 2 * len + 1; i++)
    {
        if(p[maxp] + maxp > i)
            p[i] = min(p[2 * maxp - i], p[maxp] + maxp - i);
        else
            p[i] = 1;
        while(s[i - p[i]] == s[i + p[i]])
            p[i]++;
        if(p[maxp] + maxp < i + p[i])
            maxp = i;
        if(ans < p[i])
            ans = p[i];
    }
    return ans - 1;
}
int main()
{
    int max1;
    while(gets(s))
    {
        max1=0;
        while(strlen(s)>1)
        {
            memset(p,0,sizeof(p));
            strcpy(ss,s);
            max1=max(max1,Manacher(ss));
            dif(s,res);
            strcpy(s,res);
            if(max1>=strlen(s)) break;
        }
        printf("%d
",max1);
    }
    return 0;
}
原文地址:https://www.cnblogs.com/gaojupeng/p/4484925.html