求解一最优算法

hawk2012

找出一个字符串中最长的“回文”子串。所谓回文就是对称的字符串，比如A, ABA, ABBA这些都是回文字符串。
该题目比如：acdbbdf ，那么最长的 “回文”子串是 dbbd; addbsbdf 那么最长的回文子串是 dbsbd。
请高手给出算法。

anthony1983

用分治算法能解决
不知道最优不？

guhan010

用栈,每次比较和栈顶一样的,若一样出栈向下比较,一直到不一样.
如果不一样,记录该次比较字符串首地址,和字符串长度.
然后把字符串再压回栈,继续向下,一次就搞定.

fzbook

#include <stdio.h>
#include <string.h>

int getMaxStr(const char* src,char* dest) {
        int len=strlen(src);
        int start=0;
        int max=0,inc=0,add=0;
        for(int i=0;i<len;i++) {
                inc=len-i;
                /*
                对称的时候
                */
                for(add=0;add<inc;add++) {
                        if(i-add<0) {
                                break;
                        }
                        if(src[i-add]!=src[i+add]) {
                                break;
                        }
                }
                inc=2*(add-1)+1;
                if(max<inc) {
                        max=inc;
                        start=i-add+1;
                }
                /*
                无中间值的对称
                */
                inc=len-i-1;
                for(add=0;add<inc;add++) {
                        if(i-add<0) {
                                break;
                        }
                        if(src[i-add]!=src[i+add+1]) {
                                break;
                        }
                }
                inc=2*add;
                if(max<inc) {
                        max=inc;
                        start=i-add+1;
                }
        }
        memset(dest,0,max+1);
        strncpy(dest,src+start,max);
        return max;
}

int main(int argc,char** argv) {
        if(argc!=2) {
                printf("Usage:%s 字符串\n",argv[0]);
                return 0;
        }
        printf("输入的字符串为：[%s]\n",argv[1]);
        int len=strlen(argv[1]);
        char* dest=new char[len+1];
        len=getMaxStr(argv[1],dest);
        printf("结果为：[%s]，长度为：[%d]\n",dest,len);
        return 1;
}

[[i] 本帖最后由 fzbook 于 2007-11-1 14:44 编辑 [/i]]