leetcode 5 -- Longest Palindromic Substring

原 作者 王伟豪 | 发表于 | 分类于 2013级

Longest Palindromic Substring

题目：
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

题意：
求一个字符串中的最长回文字串，回文串类似abccba或者abcba这种。

思路：
1.朴素比较每一个子串，时间复杂度为O(n^3)
2.把每个字符都当作中点，向两侧扩散，时间复杂度为O(n^2)
3.后缀树或者后缀数组来解决，把字符串后缀读进一棵树，然后逆向该字符串，再次读进这棵树，因为回文有个定义是一个字符串反向后还等于原字符串为回文串，那么比较树中重合的即可，然后记录选择最大的为最长回文串，没具体实现过，只知道大概思路。
4.类似KMP的算法，没研究，感兴趣可查下，时间复杂度为O(nlogn)。
5.Manacher算法，时间复杂度为O(n)!!!，既然是最优的算法，就来研究下哈~

5.Manacher算法思路：

1.回文串分为奇数回文串abcba和偶数回文串abccba，我们通过给字符串每个字符间隙添加特殊字符来保证所求回文串全部是奇数回文串#a#b#c#c#b#a#，如果原本数偶数字符串那么加上特殊字符后就编程以特殊字符为中心的奇数字符串。
2.我们通过回文串的特性来找最长回文串，首先维护一个len数组，数组中的每个元素是对应字符的回文串长度，那么有些字符 Po 的回文串的最右端点可延伸到另外一些字符 i 的回文串最右端点外(Po < i，po和i都是下标，简单来说也就是坐标Po < i，但是Po的回文长度却大于 i 的回文串长度，且包含进去 i ，看下图好理解)。那么就可能可以利用回文串的特性来避免 i 的回文匹配。
3.但是2中所说要分3种情况。
看下图：
图片来源http://blog.csdn.net/dyx404514/article/details/42061017
这位前辈也写的很清楚

这里写图片描述

看上图，以Po为中心的回文串已经延伸到p处了，那么当我们该计算 i 的回文串时，它所对应的回文串 j 已经计算过了，那么利用回文串的反向不变性我们可以得出 i 的回文串，是和 j 对应的。但是如果 i 的回文串半径大于p-i这段，那么超出的部分就需要继续匹配。

这里写图片描述

第二种情况是该匹配的字符 i 在Po（右端最大的回文串中点）右端点之外，那么对于 i 只能老老实实匹配。

代码：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

int min(int a, int b){
    return a<b ? a:b;
}

char * longestPalindrome(char *s){
    int length = strlen(s);
    const int N = 2*length+1;
    char a[N];
    int len[N];
    int i;
    a[0] = '@';
    a[1] = '#';
    for(i = 0; i < length; ++i){
        a[2*i+2] = s[i];
        a[2*i+3] = '#';
    }
    a[2*length+2] = '\0';
    printf("%s\n", a);

    int RightMax = 0;//最大右边值
    int MaxLen = 0;//最大长度
    int po = 0;//最大长度的中间节点
    for(i = 0; i < N; i++){
        //说明可以不匹配或者匹配剩余
        if(RightMax > i){
            len[i] = min(RightMax-i, len[2*po-i]);
        }else{
            //需要自己匹配
            len[i] = 1;
        }
        while(a[i-len[i]] == a[len[i]+i]){
            len[i]++;
        }
        //是否需要更新右边最大坐标值
        if(len[i]+i > RightMax){
            RightMax = len[i]+i;
            po = i;
        }
        if(len[i] > MaxLen){
            MaxLen = len[i];
        }
    }
    printf("%d\n", MaxLen-1);
    printf("%d\n", po);
    char p[1000];
    int j;
    //提取结果字符串
    for(i = po-MaxLen+1, j = 0; i < po+MaxLen; ++i){
        printf("%c",a[i]);
        if(a[i] != '#'){
            p[j] = a[i];
            j++;
        }
    }
    printf("\n");
    p[j] = '\0';
    printf("%s\n", p);
}

int main(int argc, char *argv[])
{
    char *s = "zeusnilemacaronimaisanitratetartinasiaminoracamelinsuez";
    char *p = longestPalindrome(s);

    return EXIT_SUCCESS;
}

这里写图片描述