算法-字符串回文问题

Question

回文就是正着看和分着看是一样的，比如aba。
现在问题是，给定一个字符串，如何判断该字符串是否是回文？
问题二：如何找出给定字符串中最大的回文子串？
问题三：如果找出给定字符串中所有的回文子串？

Answer 1

第一题....
第2,3 有大牛说 用后缀数组就可以做了...

#include <iostream>
using namespace std;

//用于qsort的比较函数
int pstrcmp(const void *p, const void *q)
{
return strcmp(*(char**)p,*(char**)q);
}

//最长公共前缀
int comlen_suff(char * p, char * q)
{
int len = 0;
int count = 0; //保证两个子串中只有一个含有‘#’，LCS才来自两个字符串，否则可能来自同一个字符串
while(*p && *q && *p++ == *q++)
{
++len;
if(*p == '#' || *q == '#')
{
break;
}
}
while(*p)
{
if(*p++ == '#')
{
++ count;
break;
}
}
while(*q)
{
if(*q++ == '#')
{
++ count;
break;
}
}
if(count == 1)
return len;
return 0;
}

//最长回文子串
int LPS(char * X)
{
char * suff[999];
int maxlen = 0;
int suf_index;
int xlen = strlen(X);
int len_suff = 2 * xlen + 1;
char * arr = new char[len_suff + 1]; // 将X和逆序X连接到一起
strcpy(arr,X);
arr[xlen] = '#';
char *p = X;
char *q = arr + len_suff;
*q = '';
while(*p && (*--q = *p++)); // 逆序复制
for(int i = 0; i < len_suff; ++i) // 初始化后缀数组
{
suff[i] = &arr[i];
}
qsort(suff, len_suff, sizeof(char *), pstrcmp);
for(int i = 0; i < len_suff-1; ++i)
{
int len = comlen_suff(suff[i],suff[i+1]);
if(len > maxlen)
{
maxlen = len;
suf_index = i;
}
}
printf("%.*sn", maxlen, suff[suf_index]);
delete[] arr;
return maxlen;
}

int main()
{
cout<<LPS("aabaab")<<endl;
return 0;
}

参考::
点我

Answer 2

Manacher算法, 时间复杂度O(N).

http://www.felix021.com/blog/read.php?2040

具体到楼主问题:
问题一: 给定一个字符串，如何判断该字符串是否是回文？
-- 这个直接从字符串首尾 向中间作比较就可以了吧.

问题二：如何找出给定字符串中最大的回文子串？
-- Manacher算法, 见链接. 得到P数组后, 求最大回文代码如下:

 int max_len=0,max_id=0;
for(i=1;i<t_len;i++)
if(p[i]>max_len){
max_len=p[i]-1;
max_id=i;
}
char *result=(char*)malloc(max_len+1);
int pos=(max_id-max_len-1)/2;
for(i=0;i<max_len;i++)result[i]=str[pos++];
result[max_len]='';
printf("result=%sn",result);

问题三：如果找出给定字符串中所有的回文子串？
-- 在Manacher得出P辅助数组后, 遍历P数组. 得到所有的回文子串, 如下:

  int j;
for(i=1;i<t_len;i++){
if(p[i] > 2)
for(len=p[i]-1;len>1;len=len-2){
result=(char*)malloc(len+1);
pos=(i-len-1)/2;
for(j=0;j<len;j++)result[j]=str[pos++];
result[len]='';
printf("a palindrome:%sn",result);
}
}

输入字符串:331256521434, 结果:
331256521434
$#3#3#1#2#5#6#5#2#1#4#3#4#
max result=1256521
a palindrome:33
a palindrome:1256521
a palindrome:25652
a palindrome:565
a palindrome:434

Answer 3

看起来是裸的后缀数组？？？

Answer 4

第二个和第三个其实就是按照第一个来做就行，无非就是加上存储当前的回文串以及长度，用来与下一个比较。而第一个问题，我想你用java来实现吧。
下面的这个是我临时写的，可能会有点小错误，但是方向是对的，课参考：

Scanner input = new Scanner(System.in);

StringBuffer sb = new StringBuffer();
StringBuffer sbr = new StringBuffer();

sb.append(input.next());

sbr = sb;

sbr.reverse();

System.out.println(sbr.equals(sb));