河南省第四届acm省赛 Substring

「爱情、让人受尽委屈。」 2022-08-22 01:17 169阅读 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

来源

[第四届河南省程序设计大赛][Link 1]

上传者

[张云聪][Link 2]

题意：

找出最早出现一个最长子串反过来也是该字符串的子串

\#include <cstdio>  
\#include <cstring>  
int main()  
\{  
    int t;  
    scanf("%d",&t);  
    while(t--)  
    \{  
        char str\[100\];  
        char a\[100\],a1\[100\], a2\[100\];  
        int maxv = -2;  
        //getchar();  
        scanf("%s",str);  
        int len,j,k,i;  
        int p;  
        len=strlen(str);  
        for( k = 0; k < len; k++)  
        \{  
            for( i = 1; i <= len - k; i++)//子串的开始位置  
            \{  
                p=0;  
                for(j = k; j < k + i; j++)//把字符串赋值给a数组  
                \{  
                    a\[p\]=str\[j\];  
                    // printf("%c",a\[p\]);  
                    p++;  
  
  
                \}  
                //printf("\\n");  
                for(j = 0 ; j < p ; j++)//将字符串逆过来  
                \{  
                    a1\[j\] = a\[p-1-j\];  
  
  
                \}  
                int s = 0, s1 = 0;  
                for(j = 0 ; j < len ; j++)//判断该子串是否在原字串内  
                \{  
                    if(s == p)//说明匹配完成。  
                        break;  
                    if(str\[j\] == a1\[s1\])  
                    \{  
                        s++;  
                        s1++;  
                    \}  
                    else  
                    \{  
                        s = 0;  
                        s1 = 0;  
                    \}  
  
  
                \}  
                if(s == p)  
               \{  
                  if(maxv < p)//将其记录下来  
                  \{  
                    maxv = p;  
                    for(j=0;j<maxv;j++)  
                    \{  
                        a2\[j\]=a\[j\];  
                    \}  
                  \}  
               \}  
            \}  
        \}  
        for(i=0;i<maxv;i++)  
           printf("%c",a2\[i\]);  
        printf("\\n");  
    \}  
  
  
    return 0;  
\}

[Link 1]: http://acm.nyist.net/JudgeOnline/search_result.php?source=%E7%AC%AC%E5%9B%9B%E5%B1%8A%E6%B2%B3%E5%8D%97%E7%9C%81%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E5%A4%A7%E8%B5%9B
[Link 2]: http://acm.nyist.net/JudgeOnline/profile.php?userid=%E5%BC%A0%E4%BA%91%E8%81%AA