2013年09月21日

最长回文子串


题目描述如下:

回文串是指形如abcbaabba 这样形式的字符串,正反读此串都是一样的。回文串如前面的例子存在两种形式,总共奇数字符的形式,总共偶数字符的形式,但都是高度对称的。给定一个字符串,查找该字符串中最大的回文子串。例如,abacdfdcaef, 则最长的回文子串是acdfdca.

分析

首先可以参考以下几个链接,以便了解回文子串中的O(n)解法。

勇幸的博客,介绍了多种关于回文子串的算法 最长回文子串O(n)的解法

我们主要关注其中O(n)的这种巧妙解法。

1.首先将回文串做一定的转换,将奇偶两种情况一并统一,采用的方式是在原字符串中插入一个特殊字符#,这样就所有的情况都转换成奇数情况了。 2.利用回文串的对称特性,减少比较次数。例如对于abcba,如果我们已经知道了以第一个b为中心的回文子串长度为1,以c中心的回文子串长度为3,那么对于第二个b,就可以直接知道以它为中心的回文串长度也是1。这是因为对称性。 3.有了对它的对称性的基本了解,就可以理解O(n)的算法了,使用数组记录以每个字符为中心的回文串往右的长度,本身是1。例如,abcba,则分别是1,1,3,1,1。以mx记录当前最长回文子串所能到达的最右边。id记录当前的最大的回文子串的中心字符的位置。 4. 关于表达式2*id - i,表示的就是以id为中心的关于i的对称点j。例如id = 5, i = 7, 那么2*id - 7 = 3,3 是以5为中心,7的对称点。

代码

有了这些基本的知识点之后,就可以写下面的代码。并且我们知道数组中记录的每个字符为中心的回文串往右的长度,所以实际的回文串长度应该是数组中的数字减一。

代码如下:

#include<iostream>
#include<cstring>
#include<iterator>

using namespace std;

int min(int left, int right){
    return left < right ? left : right; 
}

int maxmanachersubstring(char *str, int len){
    if(str == NULL || len <= 0)
        return -1;
    int newlen = 2*len + 1; 
    char *newstr = new char[newlen];
    int i = 0;
    for(i; i < len; i++){
        newstr[2*i] = '#';
        newstr[2*i+1] = str[i];
    }
    newstr[2*i] = '#';

    int *record = new int[newlen];
    memset(record,0,sizeof(int)*newlen);
    int max = 0, id = 0;

    for(i = 0; i < newlen; i++){
        record[i] = max > i ? min(record[2*id - i], max - i) : 1;
        while(i - record[i] >= 0 && i + record[i] < newlen && 
                newstr[i+record[i]] == newstr[i-record[i]]){
            ++record[i];
        }
        if(i + record[i] > max){
            max = i + record[i];
            id = i;
        }
    }

    copy(record,record+newlen,ostream_iterator<int,char>(cout," "));
    cout << endl;

    max = 0;
    for(i = 0; i < newlen; ++i){  // the max record - 1 will the max sub manacher string
        if(max < record[i]){
            max = record[i];
            id = i;
        }
    }

    delete [] record;
    return max - 1;
}

int main(){
    char str[] = {"abcdcfcdcbcdcfc"};    
    //char str[] = {"abcba"};
    //char str[] = {"abba"};
    cout << str << endl;
    cout << maxmanachersubstring(str,strlen(str)) << endl;
    return 0;
}

总结

关于O(n)的解法,需要深刻的理解回文串的对称性,利用对称性来减少比较次数。

前一篇: Openstack Vnc Console配置 后一篇: 打印螺旋矩阵