第四届河南省ACM SUBSTRING 字符串处理

SUBSTRING

时间限制: 1 Sec 内存限制: 128 MB

提交: 17 解决: 5

[提交][状态][讨论版]

题目描述

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 tiebreaker 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     ABCABAXYZXCVCX

样例输出

ABAXXCVCX

提示

来源

第四届河南省大学生程序设计竞赛

题目大意：

这道题很容易直接堪称求最长回文子串的题目。但是题目中有一句关键的话。The substring and its reversal may overlap partially or completely.

所以，实际题目的意思是将找到的子串在原串中翻转仍旧出现在原串中。审题很重要。

思路：

字符串最多50个字符，直接爆就好了。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

using namespace std;

int main() {

    int t;

    cin>>t;

    while(t--) {

        string s;

        cin>>s;

        int s_len=s.length();

        string ss;

        string str;

        for(int i=0;i<s_len;i++) {

            for(int j=1;j<=s_len-i;j++) {

                ss=s.substr(i,j);

                reverse(ss.begin(),ss.end());

                if(s.find(ss)!=-1) {

                    if(ss.length()>str.length()) {

                        reverse(ss.begin(),ss.end());

                        str=ss;

                    }

                }

            }

        }

        cout<<str<<endl;

    }

    return 0;

}

巴特西

第四届河南省ACM SUBSTRING 字符串处理

SUBSTRING

题目描述

输入

输出

样例输入

样例输出

提示

来源

最新文章

热门文章