题目如下
读入一个全由小写英文构成的字符串, 求出其中最长的回文子串. 回文串是指正着看和倒着看相同, 如abba和yyxyy.
Standard Input
有多组测试数据。第一行是整数T (T <= 100),表示测试数据的组数,随后有T组测试数据。每一组测试数据占一行,是一个长度不超过1000的全由小写英文构成的字符串.
Standard Output
对应每组输入,输出最长回文子串. 如果有多个最长子串, 则输出下标最小的那个.
题目给出了一组案例如下
Input
Output
cddc
aa
abcdcba
a
cdc
以下是我的代码
#include
#include
int main()
{
int before, after;
int t;
char str[100][1000];
char answer[100][3] = { 0 };
scanf("%d", &t);
for (int i = 0; i < t; i++)
{
scanf("%s", str[i]);
//判断偶数最大回文
for (int k = 1; k < strlen(str[i]);k++)
{
before = k - 1;
after = k;
while (before >= 0 && after < strlen(str[i]) && str[i][before] == str[i][after])
{
if (answer[i][2] == 0 || after-before+1>answer[i][2])
{
answer[i][0] = before;
answer[i][1] = after;
answer[i][2] = after - before + 1;
}
/*if (after - before + 1 == answer[i][2])
{
int s1 = 0, s2 = 0;
for (int m = 0; m < after-before+1; m++)
{
s1 += str[i][m+before];
s2 += str[i][answer[i][0] + m];
}
if (s2 > s1)
{
answer[i][0] = before;
answer[i][1] = after;
answer[i][2] = after - before + 1;
}
}*/
before--;
after++;
}
}
//奇数
for (int k = 1; k < strlen(str[i]); k++)
{
before = k - 1;
after = k + 1;
while (before >= 0 && after < strlen(str[i]) && str[i][before] == str[i][after])
{
if (answer[i][2] == 0 || after - before + 1 > answer[i][2])
{
answer[i][0] = before;
answer[i][1] = after;
answer[i][2] = after - before + 1;
}
/*if (after - before + 1 == answer[i][2])
{
int s1 = 0, s2 = 0;
for (int m = 0; m < after - before + 1; m++)
{
s1 += str[i][m + before];
s2 += str[i][answer[i][0] + m];
}
if (s2 > s1)
{
answer[i][0] = before;
answer[i][1] = after;
answer[i][2] = after - before + 1;
}
}*/
before--;
after++;
}
}
}
for (int i = 0; i < t; i++)
{
if (answer[i][2] == 0)
{
for (int j = 0; j < strlen(str[i]); j++)
{
if(str[i][j][i][answer[i][0]] ||j==0)
{
answer[i][0]=j;
answer[i][2]=1;
}
}
}
}
for (int i = 0; i < t; i++)
{
for (int j = answer[i][0]; j <= answer[i][1]; j++)
{
printf("%c", str[i][j]);
}
printf("\n");
}
return 0;
}
这串代码对题目的案例输出是正确的,如下:
感谢你的解答,但是我看了这个代码运行结果好像是不正确的呀?
for (int i = 0; i < t; i++)
{
if (answer[i][2] == 0)
{
for (int j = 0; j < strlen(str[i]); j++)
{
if(str[i][j]<str[i][answer[i][0]] ||j==0)
{
answer[i][0]=j;
answer[i][2]=1;
}
}
}
}