首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Manacher算法 && Longest && Shortest Palindrome

Manacher算法 && Longest && Shortest Palindrome

原创
作者头像
大学里的混子
修改2019-02-22 17:52:51
2960
修改2019-02-22 17:52:51
举报
文章被收录于专栏:LeetCodeLeetCode

一、Manacher算法、

public static char[] mannacherString( 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 int maxLcpsLength(String str) {
        if (str == null || str.length() == 0){
            return 0;
        }
        char[] charArr = mannacherString(str);
        int[] pArr = new int[charArr.length];
        int index = -1;
        int pR = -1;
        int max = Integer.MIN_VALUE;
        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;
            }
            max = Math.max(max,pArr[i]);
        }
        return max - 1;
    }

二、214.Shortest Palindrome

Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

Example 1:

Input: "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: "abcd"
Output: "dcbabcd"

解法:

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

public static String shortestPalindrome(String s) {
    if (s == null || s.length() < 2) return s;
    StringBuffer stringBuffer = new StringBuffer(s);
    stringBuffer.reverse();
    String revStr = new String(stringBuffer);
    char[] chars = manacherStr(revStr);
    System.out.println(chars);
    int pArr [] = new int[chars.length];
    int pR = -1;
    int index = -1;
    int maxContainEnd = -1;
    for ( int i = 0 ;i < pArr.length;i++){
        pArr[i] = (pR > i) ? Math.min(pR - i ,pArr[ 2 * index - i]):1;
        while ( i + pArr[i] < pArr.length && i - pArr[i] >=0){
            if (chars[i + pArr[i]] == chars[ i - pArr[i]]){
                pArr[i]++;
            }else break;
        }
        if ( i + pArr[i] > pR){
            pR = i + pArr[i];
            index = i;
        }

        if (pR == chars.length){
            maxContainEnd = pArr[i];
            break;
        }
    }
    StringBuffer stringBuffer1 = new StringBuffer(revStr);
    for (int i = (pArr.length -(2 * maxContainEnd - 1)) /2 - 1; i >= 0;i--){
        stringBuffer1.append(stringBuffer1.charAt(i));
    }
    return String.valueOf(stringBuffer1);
}

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、Manacher算法、
  • 二、214.Shortest Palindrome
  • 解法:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档