马纳赫算法

Question

在实现最长回文子串的 Manacher 算法时是否需要使用标记符号（给定字符串中字符之间的符号）？

如果是的话，如果256个符号都用完了会怎样？

Answer 1

个人觉得算法本身已经够难了。如果您在没有标记的情况下设法做到这一点，您的代码看起来就不会很容易理解。

幸运的是没有意义。该算法适用于任何类型的数组。就像一个字符串只是一个字符数组。只需从将字符串解析为适合您选择的编码类型的数组开始，就可以了。数据类型的大小没有复杂性限制。

Answer 2

Manacher 算法使用回文的属性它是围绕中心对称的。对于奇数长度的字符串，寻找中心相对简单。将字符添加到偶数长度的字符串可确保字符串变为奇数长度。所以，如果你的字符串是偶数长度，那么有必要添加字符

Answer 3

这个问题已经有人回答了，而且已经很老了，但我发现我的回答会很有用，因为互联网上对 Manacher 算法的大部分解释都是用难以理解的术语写的。所以我实现了我自己的算法版本。其中更容易理解。除此之外，与原始算法描述的相反，您不需要使用任何标记。我在查看算法后才弄明白这一点，我认为它会很有用，因为我认为这比原始算法更有效。

分解成套路，算法就很简单了。

基本上在我的解释中，你从字符串的左边移动到右边。您跳过第一个和最后一个字符。

对于第一个字符，虽然您在循环中跳过了它，但您将它与右侧的字符进行了比较。如果匹配，则在该位置有一个长度为 2 的回文。

现在对于每个角色，你要做两件事。

假设字符不是回文的中心，开始向外匹配。为了跟踪回文长度，您需要一个值从 0 开始的变量。现在对于外向匹配循环，让我们考虑 'i' 是字符位置，然后 x 是 i，y 是 i + 1。之后每个循环，x 减去 1，y 加 1。您将尝试将 x 位置的字符与 y 位置匹配。如果匹配，则将 length 变量的值增加 2。如果不匹配，则跳出此循环。如果这个回文的长度比你创建的最长回文的长度长，用这个循环的长度替换最长的长度。
假设'i'位置的字符是一个回文的中心。为此，循环几乎与 2 的循环相同，除了回文变量的长度现在从 1 开始。x 现在将从 'i' - 1 开始。但是，y 仍然开始相同，并且那就是'i' + 1。其他都是一样的。

演示算法如何工作，我跳过了一些位置，否则它会太长。另外，演示下方是编程代码。

此算法已在 leetcode 上测试并通过提交。但是，我正在努力提高效率。

POS:  01234567
CHAR: abacabba
  (1) - Match next right (Only to position 0)
  (2) - Assume not center, outward match.
  (3) - Assume center, outward match.
  (PL) - Palindrome Length

  Position 0: (1) a != b (PL = 1(a))

  Position 1: (2) b != a (PL = 1(b))

              (3) center(b)
                  a(0) == a(2) (PL = 3(aba))

              Longest palindrome at this position is 3.

  Position 2: (2) a != c (PL = 1(a))

              (3) center(a)
                  b(1) != c(3) (PL = 1(a))

              Longest palindrome at this position is 1.

  .....
  Position 5: (2) b(5) == b(6)
                  a(4) == a(7) (PL = 4(abba);

              (3) center(b)
                  a(4) != b(6) (PL = 1(b);

              Longest palindrome at this position is 4.

下面是C语言的代码，我写的非常简单，只要懂一点C语言就可以翻译成几乎任何语言。

#include <stdio.h>

int main(){

    int x, y, len, lenM1, lPali, paliL, paliStart;
    // <- The demonstrate print code need word to be an array
    char word[] = "abcbcabbacba[=11=]";  
    len = 12;        // < word len
    lenM1 = len - 1; // <- Len - 1;

    /* Manacher’s Algorithm Modified */
    // Word must be at least a length of 2.
    if ( word[0] == word[1] ) {
        lPali = 2;
        paliStart = 0;   
    } else {
        lPali = 1;
        paliStart = 0;
    }

    /* The loop */
    for ( int i = 1; i < lenM1; i++ ){
        int iP1 = i+1;

        /* Assume Not Center - if palindrome length is 0 
           it is a one. But 0 is unneccessary as any single 
           character can be a palindrome.
         */
        x = i;
        y = iP1;
        paliL = 0;
        while(1){
            if ( word[x] != word[y] ) {
                /*
                 * reverse so x = start;
                 * 
                 * Take note that if paliL is 0,
                 * x will not be correct. If there isn't a need to evaluate
                 * the correct x. That is fine. As paliL with length 0 will never
                 * be assigned. That is because all strings, whether contained 
                 * a palindrome or not, will start with a value of at least 1 for lPali.
                 * Any 1 character, in a string, by itself, is a palindrome of length 1.
                 * 
                 **/

                x++;
                break;
            }
            paliL += 2;
            if ( x == 0 || y == lenM1 ) break;
            x--;
            y++;
        }

        if ( paliL > lPali ){
            lPali = paliL;
            paliStart = x;
        }

        /* Assume Center */
        x = i - 1;
        y = iP1;
        paliL = 1;
        while(1){
            if ( word[x] != word[y] ) {
                // reverse so x = start;
                x++;
                break;
            }
            paliL += 2;
            if ( x == 0 || y == lenM1 ) break;
            x--;
            y++;
        }

        if ( paliL > lPali ){
            lPali = paliL;
            paliStart = x;
        }

        if ( lPali == len ) break;
    }

    word[paliStart + lPali] = 0;
    printf("%d\n", lPali);
    printf("%s", &word[paliStart]);
    return 0;
}

马纳赫算法

Manacher's algorithm

string

algorithm

dynamic-programming

palindrome