Substring，

Substring，

描述

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

这道题不是求回文串，而是求一个公共连续子串，

因为题目是求一个字符串反转B后，某一个长度最大

                     的连续子串即在A串中又在B串中，即就是求最长公共连续子串。

                     此题即可用暴力，也可以用动态规划。

#include <stdio.h>
#include <string.h>
const int maxn = 105;
int dp[maxn][maxn];
char str[maxn], ch[maxn];
int main ( )
{
    int T, len, max, pos;
    scanf ( "%d", &T );
    while ( T -- )
    {
        max = 0;
        memset ( dp, 0, sizeof ( dp ) );
        scanf ( "%s", str );
        len = strlen ( str );
        for ( int i = len; i >= 1; i -- )
            ch[len-i] = str[i-1];
        ch[len] = '\0';
        for ( int i = 1; i <= len; i ++ )
        {
            for ( int j = 1; j <= len; j ++ )
            {
                if ( str[i-1] == ch[j-1] )
                {
                    dp[i][j] = dp[i-1][j-1]+1;  //最长连续公共子串
                    if ( max < dp[i][j] )
                    {
                        max = dp[i][j]; //找最大子串位置和长度
                        pos = i;
                    }
                }

            }
        }
        for ( int i = pos-max+1; i <= pos; i ++ )
            printf ( "%c", str[i-1] );
        printf ( "\n" );
    }
    return 0;
}

#include <stdio.h>//暴力
#include <string.h>
const int maxn = 105;
char str[maxn], ch[maxn];
int match ( int i, int j, int k )   //暴力匹配长度为k的字符
{
    for ( int l = i, r = j; l <= i+k; l ++, r ++ )
        if ( str[l] != ch[r] )
            return 0;
    return 1;
}
int main ( )
{
    int T, len, max, pos;
    scanf ( "%d", &T );
    while ( T -- )
    {
        max = -1;
        scanf ( "%s", str );
        len = strlen ( str )-1;
        for ( int i = len; i >= 0; i -- )
            ch[len-i] = str[i];
        for ( int i = 0; i <= len; i ++ )
        {
            for ( int j = 0; j <= len; j ++ )
            {
                for ( int k = 0; k <= len; k ++ )
                {
                    if ( j+k > len || i+k > len )
                        break ;
                    if ( match ( i, j, k ) )
                    {
                        if ( max < k )  //找到长度最大保存str下标
                        {
                            max = k;
                            pos = i;
                        }
                    }
                }
            }
        }
        for ( int i = pos; i <= pos+max; i ++ )
            printf ( "%c", str[i] );    //输出也是str,因为保存的是str的下标
        printf ( "\n" );
    }
    return 0;
}