回文串，忽略大小写，标点符号和空格。 很傻的用了分治法，应该是白用的。就现在代码请大神改改
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#define MAXN 5000 + 10

char buf[MAXN];
int postion = 0;
int max = -1;
int common;
int templeft;
int tempright;
int finalleft = 0;
int finalright = 0;
int stringlength;

int search(int start, int end, char *str);

int main()
{
int length;
int i;
gets(buf);
length = strlen(buf);
stringlength = length;
// for(i = length; i < MAXN; i++)
// buf[i] = '\0';
search(0, length-1, buf);

printf("\tmax = %d\n", max);
printf("\tpostion = %d\n", postion);
printf("\tfinalleft = %d\n", finalleft);
printf("\tfinalright= %d\n", finalright);

for(i = postion-finalleft; i <= postion+finalright; i++)
{
printf("%c", buf[i]);
}
printf("\n");
return 0;
}

int search(int start, int end, char *str)
{
if(start > end)
return 0;

int middle = (start + end) / 2;
templeft = 0;
tempright = 0;

if(0 ==(end-start) % 2) //right
{
common = 1;
while(1)
{
while(!isalpha(str[middle-templeft]))
templeft++;
while(!isalpha(str[middle+tempright]))
tempright++;
if(middle-templeft-1 < 0 || middle+tempright+1 > stringlength)
break;
if(toupper(str[middle - templeft - 1]) == toupper(str[middle + tempright + 1]))
{
templeft++;
tempright++;
common++;
// printf("odd : %d %d\n", templeft, tempright);

}
else
break;
}
if(common > max)
{
max = common;
finalleft = templeft;
finalright = tempright;
postion = middle;
}
}
else
{
common = 0;
tempright++;
while(1)
{
if(middle-templeft < 0 || middle+tempright > stringlength)
break;
while(!isalpha(str[middle-templeft]))
templeft++;
while(!isalpha(str[middle+tempright]))
tempright++;
if(toupper(str[middle - templeft]) == toupper(str[middle + tempright]))
{
templeft++;
tempright++;
common++;
// printf("even : %d %d\n", templeft, tempright);
}
else
break;
}
if(common > max)
{
max = common;
finalleft = templeft-1;
finalright = tempright-1;
postion = middle;
}
}
search(start, middle-1, str);
search(middle+1, end, str);
}

[解决办法]
意思是检测一个字符串是否是回文串？

引用:

Quote: 引用:

代码写得还可以，要实现的是什么功能？

想实现回文串的作用，一开始以为分治法可以提高时间效率，后来发现其实和一个个遍历过去感觉是差不多的。 Madam, I'm adam。这种就错了。题目是算法竞赛入门经典上的例3-4。大一的，谢谢指导。

[解决办法]
两个指针p1指向头字符，p2指向尾字符，循环中判断*p1是否等于*p2,不等立即返回false，否则p1++,p2--。
[解决办法]
你要从中间往两边找的话, 需要先把非字母的字符过滤掉再开始找才行. 否则你一开始计算的那个中间位置就是错的. 在 main 的 search 前加一段过滤的:

int j = 0;
for(i = 0; i < length; ++i)
{
if(isalpha(buf[i]))
{
buf[j++] = buf[i];
}
}

length = j;
buf[j] = 0;

或者你可以选择从两边往中间找.