NYOJ 308

客官°小女子只卖身不卖艺 2022-06-17 13:20 166阅读 0赞

## Substring ##

时间限制： 1000 ms  |  内存限制： 65535 KB

难度： 1

描述

You are given a string input. You are to find the longest substring of input such that the reversal of the substring is also a substring of input. In case of a tie, return the string that occurs earliest in input.

Note well: The substring and its reversal may overlap partially or completely. The entire original string is itself a valid substring . The best we can do is find a one character substring, so we implement the tie-breaker rule of taking the earliest one first.

输入

The first line of input gives a single integer, 1 ≤ N ≤ 10, the number of test cases. Then follow, for each test case, a line containing between 1 and 50 characters, inclusive. Each character of input will be an uppercase letter ('A'-'Z').

输出

Output for each test case the longest substring of input such that the reversal of the substring is also a substring of input

样例输入

3                   
    ABCABA
    XYZ
    XCVCX

样例输出

ABA
    X
    XCVCX

读懂题目要求最重要，题目意思并不是最大回文字符串，

给你一个字符串a，它的一个字串的反串也是它的字串，求出这个得最长字串。

自己当时做的时候理解有误。。刚好测试数据和最大回文字符串一样，有点尴尬。

附上这道题的最优解，比较巧妙

类似于动态规划的方法去求解的

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int n,l,i,j,k,max;
        char a[55],b[55],c[55][55];
        scanf("%d",&n);
        while(n--)
        {
            max=0;
            memset(c,0,sizeof(c));
            getchar();
            scanf("%s",a);
            l=strlen(a);
            for(i=0; i<l; i++)
                b[i]=a[l-i-1];
            for(i=1; i<=l; i++)
                for(j=1; j<=l; j++)
                    if(a[i-1]==b[j-1])
                    {
                        c[i][j]=c[i-1][j-1]+1;
                        if(max<c[i][j])
                        {
                            max=c[i][j];
                            k=i;
                        }
                    }
            for(i=k-max; i<k; i++)
                printf("%c",a[i]);
            printf("\n");
        }
        return 0;
    }