求解一最優(yōu)算法

hawk2012

找出一個(gè)字符串中最長(zhǎng)的“回文”子串。所謂回文就是對(duì)稱的字符串，比如A, ABA, ABBA這些都是回文字符串。
該題目比如：acdbbdf ，那么最長(zhǎng)的 “回文”子串是 dbbd; addbsbdf 那么最長(zhǎng)的回文子串是 dbsbd。
請(qǐng)高手給出算法。

anthony1983

用分治算法能解決
不知道最優(yōu)不？

guhan010

用棧,每次比較和棧頂一樣的,若一樣出棧向下比較,一直到不一樣.
如果不一樣,記錄該次比較字符串首地址,和字符串長(zhǎng)度.
然后把字符串再壓回棧,繼續(xù)向下,一次就搞定.

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;
                /*
                對(duì)稱的時(shí)候
                */
                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;
                }
                /*
                無中間值的對(duì)稱
                */
                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("結(jié)果為：[%s]，長(zhǎng)度為：[%d]\n",dest,len);
        return 1;
}

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