首页 > 算法 数据结构 > 最长回文子串

最长回文子串

2012年7月3日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

题:给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度。回文就是正反读都是一样的字符串,如aba, abba等。

例如:aaaa与abab:最长的回文串长度分别为4、3。

解法一:(该解法有误,见勘误)

最先考虑到,这又是一个后缀数组的应用,一个字符串X如果含有回文子串,那么在其后面“连接”一个逆序X’, 类似最长公共子串的解决方法,通过后缀数组寻找,这个最长回文子串必然会出现两次,类似的,我们将串X变为X#X’,其中X’是X的逆序序列。之后的实现跟最长公共子串就基本一样了,代码如下:

/* 最长回文子串 LPS */

int maxlen;  // 记录最长回文子串的长度

/* 后缀数组 */
char * suff[100];

int pstrcmp(const void *p, const void *q)
{
	return strcmp(*(char**)p,*(char**)q);
}

int comlen_suff(char * p, char * q)
{
	int len = 0;
	while(*p && *q && *p++ == *q++)
	{
		++len;
		if(*p == '#' || *q == '#')
		{
			break;
		}
	}
	int count = 0;
	while(*p)
	{
		if(*p++ == '#')
		{
			++count;
			break;
		}
	}
	while(*q)
	{
		if(*q++ == '#')
		{
			++count;
			break;
		}
	}
	if(count == 1)
		return len;
	return 0;
}

void LPS_suffix(char * X, int xlen)
{
	maxlen = 0;

	int len_suff = 2 * xlen + 1;
	char * arr = new char [len_suff + 1];  /* 将X和逆序X连接到一起 */
	strcpy(arr,X);
	arr[xlen] = '#';

	char *p = X, *q = arr + len_suff;  /* 逆序复制 */
	*q = '\0';
	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;
		}
	}
}

这种方法的复杂度还是比较高的,大于nlgn,甚至接近于n^2,我查了一下,网上存在着O(n)的解法,实现很巧妙,详见参考资料。

解法二:

这种解法很巧妙,我看了好久才明白,具体算法见参考资料,这二人的博客已经写的很详细了,图文并茂,这里就不重述了,直接上代码了,要注意的是:参考资料博文中的mx和id分别记录最大回文子串的长度和下标位置。

/* O(n)解法 */
#define MIN(a,b) ((a) < (b) ? (a) : (b))

int maxid;        // 最长回文子串下标
int LPS_rb[100];  // i为中心的回文子串右边界下标right border
char str[100];    // 原字符串处理后的副本

void LPS_linear(char * X, int xlen)
{
	maxlen = maxid = 0;

	str[0] = '$';  // 将原串处理成所需的形式
	char *p = str;
	*(++p)++ = '#';
	while((*p++ = *X++) != '\0')
	{
		*p++ = '#';
	}

	for(int i = 1; str[i]; ++i)  // 计算LPS_rb的值
	{
		if(maxlen > i)          // 初始化LPS[i]
		{
			LPS_rb[i] = MIN(LPS_rb[2*maxid-i],(maxlen-i));
		}else
		{
			LPS_rb[i] = 1;
		}
		while(str[i-LPS_rb[i]] == str[i+LPS_rb[i]]) // 扩展
		{
			++LPS_rb[i];
		}
		if(LPS_rb[i]-1 > maxlen)
		{
			maxlen = LPS_rb[i]-1;
			maxid = i;
		}
	}
}

给出测试用例:

void main()
{
	char X[30];  // 设串不超过30
	/* test case
	 * aaaa
	 * abab
	 */
	while(cin.getline(X,30))
	{
		/* 后缀数组方法 */
		LPS_suffix(X,strlen(X));
		printf("%d\n", maxlen);

		/* O(n)方法 */
		LPS_linear(X,strlen(X));
		printf("%d\n", maxlen);
	}
}

勘误:感谢 @鼻子很帅的猪,的确如他所说,解法一是有问题的,这里给出O(n^2)的解法一,使用动态规划来做

思想:DP的考虑源于暴力方法,暴力方法是寻找一个字符串的所有子串,需要O(n^2)的开销,然后对于每一个子串需要O(n)的开销来判断是否是回文,故暴力方案为O(n^3),但是这里有一个问题,就是在暴力的时候有重复判断;

例如,如果子串X为回文,那么sXs也是回文;如果X不是回文,那么sXs也不是回文;另外,ss也是回文。所以这里使用DP我们可以按照子串长度从小到大的顺序来构建DP状态数组,使用一个二维数组dp[i][j]记录子串[i-j]是否为回文子串,那么我们就有初始化和自底向上的方案了;

初始化:单字符串和相等的双字符串为回文

自底向上构造:X[i]==X[j] && dp[i+1][j-1]==1 则dp[i][j] = 1

代码如下:

#include <iostream>
using namespace std;

/* 最长回文子串 LPS - DP */

int maxlen;  // LPS长度

/* DP解法 */
bool dp[31][31]; // dp[i][j]记录子串[i-j]是否构成回文

void LPS_dp(char * X, int xlen)   // 略去测试X合法性
{
    maxlen = 1;

    for(int i = 0; i < xlen; ++i) // 初始化
    {
        dp[i][i] = 1;       // 单字符为回文
		if(i && (X[i-1] == X[i]))
		{
			dp[i-1][i] = 1; // 双字符串为回文
		}
    }

    for(int len = 2; len < xlen; ++len)
    {
        for(int begin = 0; begin < xlen-len; ++begin)
        {
            int end = begin + len; // 从长度为3开始

            if((X[begin]==X[end]) && (dp[begin+1][end-1]==1))
            {
                dp[begin][end] = 1;
                if(end - begin + 1 > maxlen)
                {
                    maxlen = end - begin + 1;
                }
            }
        }
    }
}

void main()
{
    char X[30];  // 设串不超过30
    /* test case
     * abcfdcba / abba / abab / aaaa
     */
    while(cin.getline(X,30))
    {
        memset(dp,0,sizeof dp);
        /* DP方法 */
        LPS_dp(X,strlen(X));
        printf("%d\n", maxlen);
    }
}

再次感谢 @鼻子很帅的猪 的提醒与建议。

本节相关代码可以到这里下载。

(全文完)

参考资料:

题目:http://acm.hdu.edu.cn/showproblem.php?pid=3068

O(n)解法:

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

http://blog.csdn.net/ggggiqnypgjg/article/details/6645824

  • TLinger

    @写代码的小鬼头
    我也这样认为.

  • 写代码的小鬼头

    请问解法二中的22行与23行,是否应该用maxlen+maxid代替maxlen?

  • 小小路

    O(n)解法中if(maxlen > i)   这个式子应该永远不会成立, LPS_rb[i] = MIN(LPS_rb[2*maxid-i],(maxlen-i)) 本应当是尽量减少不必要的运算次数的,然而没起到什么作用,我看了下其他网站的做法,其中maxlen = LPS_rb[i] + i。
    ps:楼主的代码也能算出答案,只是那个 LPS_rb[i] = MIN(LPS_rb[2*maxid-i],(maxlen-i)) 没有起到作用,也就是说每次找回串的时候都是从1开始扩展的。

    • Yx.Ac

      好的,谢谢,我瞅瞅去

  • 风之谷

    楼主的文章很不错哈,9月份要找工作,打算好好看看楼主的文章...

    • Yx.Ac

      @风之谷 哈,过奖,看你思路好清晰,欢迎指正,/握手

  • 风之谷

    dp中还是存在越界吧,
    for(int len = 2; len <= xlen; ++len)
    for(int begin = 0; begin < xlen+1-len; ++begin)
    int end = begin + len;
    当len =xlen时,begin=0,此时,end就已经越界了。

    而且,因为你下面表示的子串长度是len+1,所以begin < xlen+1-len应该改为begin < xlen-len。

  • Elvin

    楼主DP解法中程序会有数组越界错误。
    比如字符串为aba, xlen=3,运行到
    len=1, begin=2时,end=3,这时X[3]已经越界了。

    • Yx.Ac

      灰常感谢,原方法不但有越界,且考虑有疏漏,现已更正,欢迎继续讨论 :-) @Elvin

  • Yx.Ac

    已勘误,改用DP,谢谢!@鼻子很帅的猪

  • 鼻子很帅的猪

    方法一应该有考虑不全的问题啊, 如果是abcfdcba这个串呢。 我觉得最长回文不应该转化成最长公共子串来解。可以用动态规划,当然最好还是manacher算法。 PS:非常欣赏楼主,要是有兴趣加我QQ 33358282, 我们做个好朋友~!~