这次重点讲Manacher算法，它是由Glenn Manacher在1975年首次发明的。Manacher算法解决的问题是在线性时间内找到一个字符串的最长回文子串，比起能够解决该问题的其他算法，Manacher算法算比较好理解和实现的。

package live.every.day.ProgrammingDesign.CodingInterviewGuide.Other;

/**
 * Manacher算法
 *
 * 【题目】
 * 给定一个字符串str，返回str中最长回文子串的长度。
 *
 * 【举例】
 * str="123"，其中的最长回文子串为"1"、"2"或者"3"，所以返回1。
 * str="abc1234321ab"，其中的最长回文子串为"1234321"，所以返回7。
 *
 * 【进阶题目】
 * 给定一个字符串str，想通过添加字符的方式使得str整体都变成回文字符串，但要求只能在str的末尾添加字符，请返回在str后面添
 * 加的最短字符串。
 *
 * 【举例】
 * str="12"。在末尾添加"1"之后，str变为"121"，是回文串。在末尾添加"21"之后，str变为"1221"，也是回文串。但"1"是所有
 * 添加方案中最短的，所以返回"1"。
 *
 * 【要求】
 * 如果str的长度为N，解决原问题和进阶问题的时间复杂度都达到O(N)。
 *
 * 【难度】
 * 相当困难
 *
 * 【解答】
 * 先说一个直观的方法。从左到右遍历字符串，遍历到每个字符的时候，都看看以这个字符作为中心能够产生多大的回文字符串。
 * 比如str="abacaba"，以str[0]=='a'为中心的回文字符串最大长度为1，以str[1]=='b'为中心的回文字符串最大长度为3，
 * ……其中最大的回文子串是以str[3]=='c'为中心的时候。这种方法非常容易理解，只要解决奇回文和偶回文寻找方式的不同就可
 * 以。比如"121"是奇回文，有确定的轴'2'。"1221"是偶回文，没有确定的轴，回文的虚轴在"22"中间。但是这种方法有明显的问题，
 * 之前遍历过的字符完全无法指导后面遍历的过程，也就是对每个字符来说都是从自己的位置出发，往左右两个方向扩出去检查。这样，
 * 对每个字符来说，往外扩的代价都是一个级别的。举一个极端的例子"aaaaaaaaaaaaaaa"，对每一个'a'来讲，都是扩到边界才停止。
 * 所以每一个字符扩出去检查的代价都是O(N)，所以总的时间复杂度为O(N^2)。Manacher算法可以做到O(N)的时间复杂度，精髓是之
 * 前字符的"扩"过程，可以指导后面字符的"扩"过程，使得每次的"扩"过程不都是从无开始。以下是Manacher算法解决原问题的过程：
 *
 * 1.因为奇回文和偶回文在判断时比较麻烦，所以对str进行处理，把每个字符开头、结尾和中间插入一个特殊字符'#'来得到一个新的
 * 字符串数组。比如str="bcbaa"，处理后为"#b#c#b#a#a#"，然后从每个字符左右扩出去的方式找最大回文子串就方便多了。对奇
 * 回文来说，不这么处理也能通过扩的方式找到，比如"bcb"，从'c'开始向左右两侧扩出去能找到最大回文。处理后为"#b#c#b#"，从
 * 'c'开始向左右两侧扩出去依然能找到最大回文。对偶回文来说，不处理而直接通过扩的方式是找不到的，比如"aa"，因为没有确定的
 * 轴，但是处理后为"#a#a#"，就可以通过从中间的#扩出去的方式找到最大回文。所以通过这样的处理方式，最大回文子串无论是偶回
 * 文还是奇回文，都可以通过统一的"扩"过程找到，解决了差异性的问题。同时要说的是，这个特殊字符是什么无所谓，甚至可以是字符
 * 串中间出现的字符，也不会影响最终的结果，就是一个纯辅助的作用。
 * 具体的处理过程请看下面代码中的manacherString方法。
 *
 * 2.假设str处理之后的字符串记为charArr。对每个字符(包括特殊字符)都进行"优化后"的扩过程。在介绍"优化后"的扩过程之前，
 * 先解释如下三个辅助变量的意义。
 * •数组pArr。长度与charArr长度一样。pArr[i]的意义是以i位置上的字符(charArr[i])作为回文中心的情况下，扩出去得到的最
 * 大回文半径是多少。举个例子来说明，对"#c#a#b#a#c#"来说，pArr[0..9]为[1,2,1,2,1,6,1,2,1,2,1]。我们的整个过程就
 * 是在从左到右遍历的过程中，依次计算每个位置的最大回文半径值。
 * •整数pR。这个变量的意义是之前遍历的所有字符的所有回文半径中，最右即将到达的位置。还是以"#c#a#b#a#c#"为例来说，还没
 * 遍历之前pR，初始设置为-1。charArr[0]=='#'的回文半径为1，所以目前回文半径向右只能扩到位置0，回文半径最右即将到达的
 * 位置变为1(pR=1)。charArr[1]=='#'的回文半径为2，此时所有的回文半径向右能扩到位置2，所以回文半径最右即将到达的位置
 * 变为3(pR=3)。charAr[2]=='#'的回文半径为1，所以位置2向右只能扩到位置2，回文半径最右即将到达的位置不变，仍是3
 * (pR=3)。charArr[3]=='a'的回文半径为2，所以位置3向右能扩到位置4，所以回文半径最右即将到达的位置变为5(pR=5)。
 * charArr[4]=='#'的回文半径为1，所以位置4向右只能扩到位置4，回文半径最右即将到达的位置不变仍是5(pR=5)。
 * charArr[5]=='b'的回文半径为6，所以位置4向右能扩到位置10，回文半径最右即将到达的位置变为11(pR=11)。此时已经到达整
 * 个字符数组的结尾，所以之后的过程中pR将不再变化。换句话说，pR就是遍历过的所有字符中向右扩出来的最大右边界。只要右边界更
 * 往右，pR就更新。
 * •整数index。这个变量表示最近一次pR更新时，那个回文中心的位置。以刚刚的例子来说，遍历到charArr[O]时pR更新，index就
 * 更新为0。遍历到charArr[1]时pR更新，index就更新为1......遍历到charArr[5]时pR更新，index就更新为5。之后的过程中，
 * pR将不再更新，所以index将一直是5。
 *
 * 3.只要能够从左到右依次算出数组pArr每个位置的值，最大的那个值实际上就是处理后的charArr中最大的回文半径，根据最大的回
 * 文半径，再对应回原字符串的话，整个问题就解决了。步骤3就是从左到右依次计算出pArr数组每个位置的值的过程。
 * 1）假设现在计算到位置i的字符charArr[i]，在i之前位置的计算过程中，都会不断地更新pR和index的值，即位置i之前的index
 * 这个回文中心扩出了一个目前最右的回文边界pR。
 * 2）如果pR-1位置没有包住当前的i位置。比如"#c#a#b#a#c#"，计算到charArr[1]=='c'时，pR为1。也就是说，右边界在1位置，
 * 1位置为最右回文半径即将到达但还没有达到的位置，所以当前的pR-1位置没有包住当前的i位置。此时和普通做法一样，从i位置字符
 * 开始，向左右两侧扩出去检查，此时的"扩"过程没有获得加速。
 * 3）如果pR-1位置包住了当前的i位置。比如"#c#a#b#a#c"，计算到charArr[6..10]时，pR都为11，此时pR-1包住了位置6~10。
 * 这种情况下，检查过程是可以获得优化的，这也是manacher算法的核心内容，如图9-14所示。
 * 在图9-14中，位置i是要计算回文半径(pArr[i])的位置。pR-1位置此时是包住位罝i的。同时根据index的定义，index是pR更新
 * 时那个回文中心的位置，所以如果pR-1位置以index为中心对称，即图9-14中的"左大"位置，那么从"左大"位置到pR-1位置一定是
 * 以index为中心的回文串，我们把这个回文串叫作大回文串，同时把pR-1位置称为"右大"位置。既然回文半径数组pArr是从左到右计
 * 算的，所以位置i之前的所有位置都已经算过回文半径。假设位置i以index为中心向左对称过去的位置为i，那么位置i的回文半径也是
 * 计算过的。那么以i为中心的最大回文串大小(pArr[i'])必然只有三种情况，我们依次来分析一下，假设以i为中心的最大回文串的左
 * 边界和右边界分别记为"左小"和"右小"。
 *
 * 情況一，"左小"和"右小"完全在"左大"和"右大"内部，即以i'为中心的最大回文串完全在以index为中心的最大回文串的内部，如图
 * 9-15所示。
 * 图9-15中，a'是"左小"位置的前一个字符，b'是"右小"位置的后一个字符，b是b'以index为中心的对称字符，a是a'以index为中
 * 心的对称字符。"左小'"是"左小"以index为中心的对称位置，"右小'"是"右小"以index为中心的对称位置。如果处在情况一下，那
 * 么以位置i为中心的最大回文串可以直接确定，就是从"右小'"到"左小'"这一段。这是什么原因呢？首先，"左小"到"右小"这一段如
 * 果以index为回文中心，对应过去就是"右小'"到"左小'"这一段，那么"右小'"到"左小'"这一段就完全是"左小"到"右小"这一段的
 * 逆序。同时有"左小"到"右小"这一段又是回文串(以i为回文中心)，所以"右小'"到"左小'"这一段一定也是回文串，也就是说，以位
 * 置i为中心的最大回文串起码是"右小'"到"左小'"这一段。另外，以位置i'为中心的最大回文串只是"右小'"到"左小'"这一段，说明
 * a'!=b'。那么与a'相等的a也必然不等于与b'相等的b，既然a!=b，说明以位置i为中心的最大回文串就是"右小'"到"左小'"这一段，
 * 而不会扩得更大。
 * 情况一举例如图9-16所示。
 *
 * 情况二，"左小"和"右小"的左侧部分在"左大"和"右大"的外部，如图9-17所示。
 * 图9-17中，a是"左大"位置的前一个字符，d是"右大"位置的后一个字符，"左大'"是"左大"以位置i为中心的对称位置，"右大'"是
 * "右大"以位置i为中心的对称位置，b是"左大'"位置的后一个字符，c是"右大'"位置的前一个字符。如果处在情况二下，那么以位置
 * i为中心的最大回文串可以直接确定，就是从"右大'"到"右大"这一段。这是什么原因呢？首先"左大"到"左大'"这一段和"右大'"到
 * "右大"这一段是关于index对称的，所以"右大'"到"右大"这一段是"左大"到"左大'"这一段的逆序。同时"左小"到"右小"这一段是
 * 回文串(以i位置为中心)，那么"左大"到"左大'"这一段也是回文串，所以"左大"到"左大'"这一段的逆序也是回文串，所以"右大'"
 * 到"右大"这一段一定是回文串。也就是说，以位置i为中心的最大回文串起码是"右大'"到"右大"这一段。另外，"左小"到"右小"这一
 * 段的是回文串，说明a==b，b和c关于index对称说明b==c,"左大"到"右大"这一段没有扩得更大，说明a!=d，所以d!=c。说明以
 * 位置i为中心的最大回文串就是"右大'"到"右大"这一段，而不会扩得更大。
 * 情况二举例如图9-18所示。
 *
 * 情况三，"左小"和"左大"是同一个位置，即以i为中心的最大回文串压在了以index为中心的最大回文串的边界上，如图9-19所示。
 * 图9-19中，"左大"与"左小"的位置重叠，"右小'"是"右小"位置以index为中心的对称位置，"右大'"是"右大"位置以i为中心的对
 * 称位置，可以很容易的证明"右小'"和"右大'"位置也重叠。如果处在情况三下，那么以位置i为中心的最大回文串起码是"右大'"和
 * "右大"这一段，但可能会扩得更大。因为"右大'"和"右大"这一段是"左小"和"右小"这一段以index为中心对称过去的，所以两段互
 * 为逆序关系，同时"左小"和"右小"这一段又是回文串，所以"右大'"和"右大"这一段肯定是回文串，但以位置i为中心的最大回文串是
 * 可能扩得更大的。比如图9-20的例子。
 * 图9-20中，以位置i为中心的最大回文串起码是"右大'"到"右大"这一段，但可以扩得更大。说明在情况三下，扩出去的过程可以得到
 * 优化，但还是无法避免扩出去的检查。
 *
 * 4.按照步骤3的逻辑从左到右计算出pArr数组，计算完成后再遍历一遍pArr数组，找出最大的回文半径，假设位置i的回文半径最大，
 * 即pArr[i]==max。但max只是charArr的最大回文半径，还得对应回原来的字符串，求出最大回文半径的长度(其实就是max-1)。
 * 比如原字符串为"121"，处理成charArr之后为"#1#2#1#"。在charArr中位置3的回文半径最大，最大值为4(即pArr[3]==4)，
 * 对应原字符串的最大回文子串长度为4-1=3。
 *
 * 证明Manacher的时间复杂度是O(N)。虽然我们可以很明显地看到Manacher算法与普通方法相比，在扩出去检查这一行为上有明
 * 显的优化，但如何证明该算法的时间复杂度就是O(N)呢？关键之处在于估算扩出去检查这一行为发生的数量。原字符串在处理后的长度
 * 由N变为2N，从步骤3的主要逻辑来看，要么在计算一个位置的回文半径时完全不需要扩出去检查，比如，步骤3的中3）介绍的情况一
 * 和情况二，都可以直接获得位置i的回文半径长度；要么每一次扩出去检查都会导致pR变量的更新，比如步骤3中的2）和3）介绍的情
 * 况三，扩出去检查时都让回文半径到达更右的位置，当然会使pR更新。然而pR最多是从-1增加到2N(右边界)，并且从来不减小，所以
 * 扩出去检查的次数就是O(N)的级别。所以Manacher算法时间复杂度是O(N)。具体实现看下面代码里的maxLcpsLength方法。
 *
 * 进阶问题。在字符串的最后添加最少字符，使整个字符串都成为回文串，其实就是查找在必须包含最后一个字符的情况下，最长的回文
 * 子串是什么。那么之前不是最长回文子串的部分逆序过来，就是应该添加的部分。比如"abcd123321"，在必须包含最后一个字符的情
 * 况下，最长的回文子串是"123321"，之前不是最长回文子串的部分是"abcd"，所以末尾应该添加的部分就是"dcba"。那么只要把
 * manacher算法稍作修改就可以。
 * 具体改成：从左到右计算回文半径时，关注回文半径最右即将到达的位置(pR)，一旦发现已经到达最后(pR==charArr.length)，
 * 说明必须包含最后一个字符的最长回文半径已经找到，直接退出检查过程，返回该添加的字符串即可。
 * 具体过程看下面代码中的shortestEnd方法。
 *
 * @author Created by LiveEveryDay
 */
public class ManacherAlgorithm2 {

    public static char[] manacherString(String str) {
        char[] charArr = str.toCharArray();
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : charArr[index++];
        }
        return res;
    }

    public static String shortestEnd(String str) {
        if (str == null || str.length() == 0) {
            return null;
        }
        char[] charArr = manacherString(str);
        int[] pArr = new int[charArr.length];
        int index = -1;
        int pR = -1;
        int maxContainsEnd = -1;
        for (int i = 0; i != charArr.length; i++) {
            pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;
            while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
                if (charArr[i + pArr[i]] == charArr[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }
            if (i + pArr[i] > pR) {
                pR = i + pArr[i];
                index = i;
            }
            if (pR == charArr.length) {
                maxContainsEnd = pArr[i];
                break;
            }
        }
        char[] res = new char[str.length() - maxContainsEnd + 1];
        for (int i = 0; i < res.length; i++) {
            res[res.length - 1 - i] = charArr[i * 2 + 1];
        }
        return String.valueOf(res);
    }

    public static void main(String[] args) {
        String str = "abc1234321ab";
        System.out.printf("The shortest string is: %s", shortestEnd(str));
    }
}

// ------ Output ------
/*The shortest string is: a1234321cba*/