求助:最长回文子串
例如:在字符串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]);
请教各位高手,如何做出?