题目链接:http://nyoj.top/problem/308

  • 内存限制:64MB 时间限制:1000ms

题目描述

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

解题思路

就是求最长的一个子串，其反转也在主串中，如果有多个输出最早的那个。数据比较小，直接暴力，一个枚举子串的长度，一个枚举子串的开头。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t, l, temp;
    char str[55], s1[55], s2[55];
    scanf("%d", &t);
    while (t--) {
        temp = 0;
        scanf("%s", &str);
        l = strlen(str);
        for (int i = l; i > 0 && !temp; i--) {
            for (int j = 0; j <= l - i && !temp; j++) {
                strncpy(s1, str + j, i);
                s1[i] = '\0';
                for (int k = 0; k < i; k++)
                    s2[k] = s1[i - k - 1];
                s2[i] = '\0';
                if (strstr(str, s2))
                    temp = 1;
            }
        }
        printf("%s\n", s1);
    }
    return 0;
}