576
NYOJ308-Substring
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
來源
第四屆河南省程序設計大賽
題意是找最長子串反過來還是其子串，不是找最長的回文串
AC代碼：
#include<stdio.h>
#include<string.h>
char a[110],b[110],c[110];
int Find(char a[],char c[],int n,int k)//判斷c字串反過來還是不是a的字串
{
int j=k-1,i=0,x=0,flag=0;
while(1)
{
if(j==-1)
{
flag=1;
break;
}
if(x>n-1)
break;
if(c[j]==a[i])
{
j--;i++;
}
else
{
j=k-1;i=x++;
}
}
return flag;
}
int main()
{
int i,j,n,m,len;
scanf("%d",&m);
while(m--)
{
scanf("%s",a);
n=strlen(a);
int flag=0;len=0;
for(i=0;i<=n-1;i++)
{
for(j=0;j<=n-1;j++)
{
if(j<=i)
{
memset(c,0,sizeof(c));
int k=0;
/*for(int p=j;p<=i;p++)
printf("%c",a[p]);
puts("");*/
for(int p=j;p<=i;p++)//找出子串
{
c[k++]=a[p];
}
if(Find(a,c,n,k)==1)//判斷子串的反串是不是仍是子串
{
if(k>len)//找到新的符合條件的並且長度比原來大的更新
{
len=0;
for(int v=0;v<k;v++)
{
b[len++]=c[v];
}
}
}
}
}
}
for(i=0;i<len;i++)//輸出最終答案
printf("%c",b[i]);
puts("");
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
}
return 0;
}
最後更新：2017-04-03 08:26:17