【算法&数据结构体系篇class28】：Manacher算法

川长思鸟来 2024-03-23 13:28 73阅读 0赞

### 一、Manacher算法核心 ###

> 1）理解回文半径数组 pArr
> 
> 2）理解所有中心的回文最右边界R，和取得R时的中心点C
> 
> 3）理解  L…(i\`)…C…(i)…R 的结构，以及根据i’回文长度进行的状况划分
> 
> 4）每一种情况划分，都可以加速求解i回文半径的过程

### 二、返回最长回文子串 ###

> 假设字符串str长度为N，想返回最长回文子串的长度
> 
> Manacher算法解决 时间复杂度O(N)

package class28;
    
    /**
     * 假设字符串str长度为N，想返回最长回文子串的长度
     *
     * 时间复杂度O(N)
     *
     * manacher算法
     *
     * 1）理解回文半径数组
     *
     * 2）理解所有中心的回文最右边界R，和取得R时的中心点C
     *
     * 3）理解   L…(i`)…C…(i)…R  的结构，以及根据i’回文长度进行的状况划分
     *
     * 4）每一种情况划分，都可以加速求解i回文半径的过程
     */
    public class manacher {
    
        //manacher算法
        public static int manacher(String s) {
            //边界判断
            if(s == null || s.length() == 0) return 0;
    
            //预处理s字符串 因为s长度有奇数 有偶数情况 为了方便 我们通过预处理给每个字符两边都加上#特殊字符
            // 比如  123321  => #1#2#3#3#2#1#  或者加任意一个与原字符相等的某个字符 1 2 都可以 因为在比较的时候 都是相隔数比较 不会与原字符比较
            char[] str = manacherString(s);
    
            //转换完成后，后续我们就是对str数组处理  我们定义 几个辅助变量
            int[] pArr = new int[str.length];    //同数组长度的辅助数组  回文半径数组 123321  当前在3 那么回文半径就是321 长度3
            int c = -1;                           //当前数组中遍历到的中心索引值 一开始默认-1 还未来到第一个
            int r = -1;                          //c中心索引值 的回文串的最右边界值的再往右一个位置 也就是 123321 当前c在3 那么r-1就在1
            int max = Integer.MIN_VALUE;         //结果返回最长回文子串长度
            //开始遍历整个数组 取出每个位置时，对应的回文半径长度
            for(int i = 0; i < str.length; i++){
                //刷新pArr数组 加速匹配的核心数组
                // 表示当前pArr[i] 能往右扩到哪里 这段区间内就是不需要判断的 可以跳过省略
                //前提判断 如果右边界包含住了i位置，也就是r>i 因为我们定义r是符合回文右边界+1位置 所以是要大于i才是把i包含在内
                //r>i 包含在边界内 那么就判断 以c当前中心点，i对称的位置i1(通过2c-i得到) 其pArr[i1]回文半径长度  与i的回文半径 r-i 两者大小 返回较小长度。就是可以跳过遍历的位置
                //如果r <= i 比如一开始 r=-1表示还没有右边界 i=0 此时 要得到i 回文子串最小至少就是i自身长度1 返回1
                pArr[i] =  r > i ?  Math.min(pArr[2*c-i],r-i) : 1;
    
                //刷新完了当前i 回文半径， 接着就判断 是否有需要再往两边扩充回文半径长度的,就在越界前进行左右两边扩充判断
                //i位置往右边扩 +回文半径pArr[i]  该长度内已经是不用判断的跳过了 接着往右下一个  左边则-
                while ( i+pArr[i] < str.length && i - pArr[i] > -1){
                    if(str[i+pArr[i]] == str[i - pArr[i] ]){
                        //如果左边两边相等 刷新回文半径长度
                        pArr[i] ++;
                    }else {
                        break; //如果没有需要扩充 那么就直接跳出循环了 表示i位置的回文半径已经刷新
                    }
                }
    
                //同时需要刷新i是否扩充了r往更右  c是否也跟着变化要刷新到对应i c跟r是一对  i=c中心位置 构成回文串最右侧边界+1 r
                //i位置加上回文串半径后来到的位置 就是新的r位置 如果新r 大于之前r 那么就是刷新r  并且c位置也落到当前i位置来
                if(i + pArr[i] > r){
                    r = i + pArr[i];
                    c = i;
                }
                max = Math.max(pArr[i],max);  //每次遍历 刷新当前位置所处于的回文串的最大半径长度
            }
    
            //因为我们str是处理过添加了#字符，此时最大值半径max-1 刚好就是原回文字符串的长度 所以最大回文串长度就是 max-1
            //比如 121 =》 #1#2#1#   str[3] 2值位置 pArr[3] 回文半径就是 2#1# =4  max = 4  max-1=3 原回文串长度121长度 3 相等
            // 1221 =》 #1#2#2#1#   str[4] #值位置 pArr[4] 回文半径就是 #2#1# =5  max = 5  max-1=4 原回文串长度1221长度 4 相等
            return max -1 ;
        }
    
        //预处理字符  123321  => #1#2#3#3#2#1#
        public static char[] manacherString(String s){
            char[] chars = s.toCharArray();
            char[] res = new char[chars.length*2 +1];  //结果集数组 长度就是原数组2倍+1
            int index = 0;                             //原数组 索引开始0
    
            //遍历原字符数组 转换到res
            for(int i = 0; i < chars.length; i++){
                //观察转换后的字符 i位置在0 2 4...偶数索引 值都是'#' 奇数位置都是原数组值
                // 利用与1运算 为1就是奇数，奇数位置就是原数组值 赋值chars[index++]  同时index++  否则就是'#'
                res[i] = (i & 1) == 1 ? chars[index++] : '#';
            }
            return res;
        }
    
        // for test
        public static int right(String s) {
            if (s == null || s.length() == 0) {
                return 0;
            }
            char[] str = manacherString(s);
            int max = 0;
            for (int i = 0; i < str.length; i++) {
                int L = i - 1;
                int R = i + 1;
                while (L >= 0 && R < str.length && str[L] == str[R]) {
                    L--;
                    R++;
                }
                max = Math.max(max, R - L - 1);
            }
            return max / 2;
        }
    
        // for test
        public static String getRandomString(int possibilities, int size) {
            char[] ans = new char[(int) (Math.random() * size) + 1];
            for (int i = 0; i < ans.length; i++) {
                ans[i] = (char) ((int) (Math.random() * possibilities) + 'a');
            }
            return String.valueOf(ans);
        }
    
        public static void main(String[] args) {
            int possibilities = 5;
            int strSize = 20;
            int testTimes = 5000000;
            System.out.println("test begin");
            for (int i = 0; i < testTimes; i++) {
                String str = getRandomString(possibilities, strSize);
                if (manacher(str) != right(str)) {
                    System.out.println("Oops!");
                }
            }
            System.out.println("test finish");
        }
    
    }

### 三、题目：已知一个字符串 ， 在其后面至少加多个字符 能使得整个字符串是一个回文串 ###

>     已知一个字符串 ， 在其后面至少加多个字符 能使得整个字符串是一个回文串
> 
>     比如 abcd123321    需要在1 后面加 bcda   构成 abcd123321dcba

package class28;
    
    /**
     * 已知一个字符串 ， 在其后面至少加多个字符 能使得整个字符串是一个回文串
     * 比如 abcd123321    需要在1 后面加 bcda   构成 abcd123321dcba
     *
     * manacher算法
     * 找到包含最后一个字符在内的最长回文子串半径 也就是pArr[i]  123321 确定了后面的最长回文串 再把前面的额abcd倒序追加到后面
     */
    public class shortestEnd {
    
        public static String shortestEnd(String s) {
            //边界判断
            if(s == null || s.length() == 0) return "";
    
            //预处理s字符串 因为s长度有奇数 有偶数情况 为了方便 我们通过预处理给每个字符两边都加上#特殊字符
            // 比如  123321  => #1#2#3#3#2#1#  或者加任意一个与原字符相等的某个字符 1 2 都可以 因为在比较的时候 都是相隔数比较 不会与原字符比较
            char[] str = manacherString(s);
    
            //转换完成后，后续我们就是对str数组处理  我们定义 几个辅助变量
            int[] pArr = new int[str.length];    //同数组长度的辅助数组  回文半径数组 123321  当前在3 那么回文半径就是321 长度3
            int c = -1;                           //当前数组中遍历到的中心索引值 一开始默认-1 还未来到第一个
            int r = -1;                          //c中心索引值 的回文串的最右边界值的再往右一个位置 也就是 123321 当前c在3 那么r-1就在1
            int maxContainsEnd = -1;                     //包含最后一个字符在内的最长回文子串半径 也就是pArr[i]
    
            //开始从头开始遍历  直到r来到了越界位置 因为r-1就是尾元素 那么就可以退出 取到pArr[i]
            for(int i = 0; i < str.length; i++){
                //刷新pArr数组 加速匹配的核心数组
                // 表示当前pArr[i] 能往右扩到哪里 这段区间内就是不需要判断的 可以跳过省略
                //前提判断 如果右边界包含住了i位置，也就是r>i 因为我们定义r是符合回文右边界+1位置 所以是要大于i才是把i包含在内
                //r>i 包含在边界内 那么就判断 以c当前中心点，i对称的位置i1(通过2c-i得到) 其pArr[i1]回文半径长度  与i的回文半径 r-i 两者大小 返回较小长度。就是可以跳过遍历的位置
                //如果r <= i 比如一开始 r=-1表示还没有右边界 i=0 此时 要得到i 回文子串最小至少就是i自身长度1 返回1
                pArr[i] = r > i ? Math.min(pArr[2*c - i],r-i): 1;
    
                //刷新完了当前i 回文半径， 接着就判断 是否有需要再往两边扩充回文半径长度的,就在越界前进行左右两边扩充判断
                //i位置往右边扩 +回文半径pArr[i]  该长度内已经是不用判断的跳过了 接着往右下一个  左边则-
                while(i + pArr[i] < str.length && i - pArr[i] > -1){
                    if(str[i+pArr[i]] == str[i-pArr[i]]){
                        //如果左边两边相等 刷新回文半径长度
                        pArr[i]++;
                    }else{
                        break;//如果没有需要扩充 那么就直接跳出循环了 表示i位置的回文半径已经刷新
                    }
                }
    
                //同时需要刷新i是否扩充了r往更右  c是否也跟着变化要刷新到对应i c跟r是一对  i=c中心位置 构成回文串最右侧边界+1 r
                //i位置加上回文串半径后来到的位置 就是新的r位置 如果新r 大于之前r 那么就是刷新r  并且c位置也落到当前i位置来
                if(i + pArr[i] > r){
                    r = i + pArr[i];
                    c = i;
                }
    
                //最后这里 关键： 判断r是否来到了越界位置 是的话 说明当前i的回文半径右边界已经到了最后一个元素 那么就可以退出 并且保存当前的回文半径
                if(r == str.length){
                    maxContainsEnd = pArr[i];   //保存包含了最后一个字符的当前回文半径长度
                    break;
                }
            }
    
            //定义一个结果集数组 长度定义就是 原字符串s长度 -  包含了最后一个字符的最长回文串长度
            //因为我们str是处理过添加了#字符，此时回文半径maxContainsEnd-1 刚好就是回文字符串的长度
            //比如 121 =》 #1#2#1#   str[3] 2值位置 pArr[3] 回文半径就是 2#1# =4  max = 4  max-1=3 原回文串长度121长度 3 相等
            // 1221 =》 #1#2#2#1#   str[4] #值位置 pArr[4] 回文半径就是 #2#1# =5  max = 5  max-1=4 原回文串长度1221长度 4 相等
            //所以包含了最后一个字符的最长回文串长度 maxContainsEnd-1
            char[] res = new char[s.length() - (maxContainsEnd - 1)];
            //赋值 就是倒序的填充原数组前面的数   比如 abcd123321    需要在1 后面加 bcda  形成整体回文
            for(int i = 0 ; i < res.length; i++){
                //数组值从后往前赋值  对应str前面开始 str是添加标记符号的处理数组 要跳过偶数索引 所以用i*2+1 表示奇数就是对应原数组字符
                res[res.length-1 - i] = str[i * 2 + 1];
            }
            //最后返回转换字符串类型
            return String.valueOf(res);
    
        }
    
        //转换函数  123321  => #1#2#3#3#2#1#
        public static char[] manacherString(String s){
            char[] chars = s.toCharArray();
            char[] res = new char[chars.length*2 + 1];    //定义结果集数组 添加了n+1个标记号
            int index = 0;                                //原数组开始索引
            for(int i = 0; i < res.length; i++){
                res[i] = (i & 1) == 0 ? '#' : chars[index++];   //填充赋值 标记号都是在偶数索引  i位置 与运算1 为0 则为偶数索引 赋值# 其他的就是原数组赋值同时index++
            }
            return res;
        }
    
        public static void main(String[] args) {
            String str1 = "abcd123321";
            System.out.println(shortestEnd(str1));
        }
    }