| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 5854 人关注过本帖, 1 人收藏
标题:求助:最长回文子串
只看楼主 加入收藏
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
结帖率:79.37%
收藏(1)
已结贴  问题点数:100 回复次数:10 
求助:最长回文子串

例如:在字符串abacbaabcccccbae 中,最长回文子串为:bcccccb 试着编写程序求一个字符串中的最长回文子串。

我贴个自己写的最长重复子串,利用后缀数组
CODE:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXCHAR 5000 //最长处理5000个字符
char c[MAXCHAR], *a[MAXCHAR];
int comlen( char *p, char *q ){
    int i = 0;
    while( *p && (*p++ == *q++) )
        ++i;
    return i;
}
int pstrcmp( const void *p1, const void *p2 ){
    return strcmp( *(char* const *)p1, *(char* const*)p2 );
}
int main(  ){
    char ch;
    int  n=0;
    int  i, temp;
    int  maxlen=0, maxi=0;
    printf("Please input your string:\n");
    while( (ch=getchar())!='\n' ){
        a[n]=&c[n];
        c[n++]=ch;
    }
    c[n]='\0';
    qsort( a, n, sizeof(char*), pstrcmp );
    for(i=0; i<n-1; ++i ){
        temp=comlen( a[i], a[i+1] );
        if( temp>maxlen ){
            maxlen=temp;
            maxi=i;
        }
    }
    printf("%.*s\n",maxlen, a[maxi]);
    system("PAUSE");
    return 0;
}
解题思路:
  对于类似从给定的文本中,查找其中最长的重复子字符串的问题,可以采用“后缀数组”

来高效地完成此任务。后缀数组使用文本本身和n个附加指针(与文本数组相应的指针数组)
来表示输入文本中的n个字符的每个子字符串。
第一,构造后缀指针数组:a[n]=&c[n];
例如:输入字符串为"banana",该数组将表示这些后缀:
 a[0]:banana
 a[1]:anana
 a[2]:nana
 a[3]:ana
 a[4]:na
 a[5]:a
第二,快速排序:qsort( a, n, sizeof(char*), pstrcmp );
经过快速排序后数组a如下:
 a[0]:a
 a[1]:ana
 a[2]:anana
 a[3]:banana
 a[4]:na
 a[5]:nana
第三,使用以下comlen函数对数组进行扫描比较邻接元素,以找出最长重复的字符串,输入:
printf("%.*s\n",maxlen, a[maxi]);

请教各位高手,如何做出?
搜索更多相关主题的帖子: 回文 
2010-12-09 19:55
freedgun
Rank: 5Rank: 5
等 级:职业侠客
帖 子:147
专家分:302
注 册:2010-11-11
收藏
得分:14 
坐等高手

有什么样的付出,就有什么样的收获!!
2010-12-09 20:08
御坂美琴
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:魔術の禁書目錄
等 级:小飞侠
威 望:9
帖 子:952
专家分:2929
注 册:2010-8-18
收藏
得分:14 
你那个是伪后缀数组构造算法,偷懒用的。。。
万一测试数据自相似程度很高,就挂了
排序的最坏情况复杂度就要O(n^2logn)了

永远为正义而奋斗,锄强扶弱的Level 5 超能力者
とある魔術の禁書目錄インデックス__御み坂さか美み琴こと
http://bbs.bccn.net/space.php?action=threads&uid=483997
2010-12-09 20:14
fightingsss
Rank: 6Rank: 6
等 级:侠之大者
帖 子:97
专家分:471
注 册:2010-11-12
收藏
得分:14 
看看。。。
2010-12-11 17:39
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
顶上去,应该枚举没问题吧

欢迎来到我的博客:http://blog..cn/noisunyuhong
2010-12-12 11:04
wujieru
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:1
帖 子:1108
专家分:1939
注 册:2010-10-9
收藏
得分:14 
枚举没问题  效率很低
2010-12-12 12:19
落拓
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:58
专家分:173
注 册:2010-9-29
收藏
得分:14 
楼主试试这个:
#include<stdio.h>
#include<string.h>

int length=0;//记录长度
int n; //字符串长度

void  fun( char *ch)
{
    int j, k, m, i, count=0 ;

    for(i=0; i < n; ++i) //从第i+1个,开始探测是否存在回文串
    {
        count = 0;
        for(k=i, m= j= n-1; k< j; )
        {
            while( (ch[k]==ch[j]) && (k<=j) ) //前后对应相同,而且,前面的指向标志k,小于后面的标志j
            {
                ++k;//向后移动一位
                --j;//向前移动一位
                ++count; //计数
            }

            if( (k>=j) && (m-i+1>length) ) //首先判断是不是回文串,然后才判断是不是比原先的长
            {
                length= m - i +1;
                break; //跳出第二个 for ,因为对于此时的 i ,length 必然是最长的一个字符串长度(j向前移,必然小)。
            }
        
            j= j+ count -1;//回头,但要比上一次循环的 j 向前移动一位
            k= i; //从头开始
            m= j; //记录此趟循环,是从字符串后面哪个字符开始的
            count= 0;//清零
   
        }

        if(length > (n-i-1) ) //n-i-1 为余下未检测的字符串的长度, 此时说明length为此字符串最长回文串
        {
            break;
        }
   
    }

}


void main()
{
    char ch[256];

    gets(ch);
       n= strlen(ch);//获取字符串长度
   
    fun(ch);
   
    if( length != 0 )
    {
        printf("最大回文串的长度为:  %d\n",length);
    }
    else
    {
        printf("此字符串不存在回文串\n");
    }
}
2010-12-12 16:25
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
程序代码:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
#define MAXN 5000
char buf[MAXN],s[MAXN];
int p[MAXN];
int main()
{
  int n,m=0,max=0,x,y;
  int i,j;   
  fgets(buf,sizeof(s),stdin);
  n=strlen(buf);
  for(i=0;i<n;i++)
   if(isalpha(buf[i]))//去掉字符串中的符号标点
   {
   p[m]=i;          //保存s[i]在buf中的位置
   s[m++]=toupper(buf[i]);  //全部转化为大写以便判断是否回文
   }
   for(i=0;i<m;i++)
   {
   //长度为奇数的回文子串 duaud
   for(j=0;i-j>=0&&i+j<m;j++)
   {
   if(s[i-j]!=s[i+j]) break;
   if(j*2+1>max){max=j*2+1;x=p[i-j];y=p[i+j];}//跟新max的同时把p[i]和p[j]保存到x,y
   }
   //长度为偶数的回文子串
    for(j=0;i-j>=0&&i+j+1<m;j++)
   {
   if(s[i-j]!=s[i+j+1]) break;
   if(j*2+2>max){max=j*2+1;x=p[i-j];y=p[i+j+1];}
   }
   }
   for(i=x;i<=y;i++)
     printf("%c",buf[i]);
     printf("\n");
   system("pause");
    return 0;
}
终于找到了刘汝佳写的最长回文子串了:

欢迎来到我的博客:http://blog..cn/noisunyuhong
2010-12-12 19:37
jyd
Rank: 2
等 级:论坛游民
帖 子:6
专家分:16
注 册:2008-11-8
收藏
得分:14 
http://www.  这个不知是否看过
2010-12-12 20:01
zdyzhang
Rank: 9Rank: 9Rank: 9
来 自:栖息地
等 级:蜘蛛侠
威 望:4
帖 子:2335
专家分:1227
注 册:2008-9-20
收藏
得分:14 
留名待以后看。

悲剧源于生活。
2010-12-13 19:10
快速回复:求助:最长回文子串
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.044573 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved