回文串，忽略大小写，标点和空格。 很傻的用了分治法，应该是白用的。就现在代码请大神改改

回文串，忽略大小写，标点符号和空格。 很傻的用了分治法，应该是白用的。就现在代码请大神改改
#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;

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

查看更多 下一篇