Tag: Manacher

Posted 2022-05-22Updated 2022-06-08LeetCode / Medium3 minutes read (About 404 words)

Question

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Solution

Manacher算法，与5. Longest Palindromic Substring的实现方法相同。

首先处理字符串。
然后采用中心拓展计算各个位置的拓展长度，并维护c与r。
每次遍历时计算结果，将当前可扩展长度加一然后除以二后加入结果。

Code

class Solution {
    int n;
    int[] p;
    String newString;
    public int countSubstrings(String s) {
        n = s.length();
        StringBuffer sb = new StringBuffer();
        if(n == 0) {   //对字符串进行处理
            sb.append("^$");
        }
        else{
            sb.append("^");
            for(int i = 0; i < s.length(); i++){
                sb.append('#');
                sb.append(s.charAt(i));
            }
            sb.append("#$");
        }
        p = new int[sb.length()];
        newString = sb.toString();
        
        return manacher();
    }
    
    private int manacher(){
        int res = 0, c = 0, r = 0;
        for(int i = 1; i < newString.length()-1; i++){
            int m = 2 * c - i;
            if(i < r) p[i] = Math.min(r-i, p[m]);
            
            while(newString.charAt(i+p[i]+1) == newString.charAt(i-p[i]-1)){    //中心拓展
                p[i]++;
            }
            
            if(i+p[i] > r){ //更新c与r
                c = i;
                r = i + p[i];
            }
            res += (p[i]+1)/2;  //向上取整
        }
        return res;
    }
}

Solution 2

中心拓展，辅助方法count()用来计算每个字符可以组成的最大回文数。

注意每次需要计算奇数长度回文和偶数长度回文两种情况。
遍历所有字符并加和，返回总数。

Code

class Solution {
    String word;
    public int countSubstrings(String s) {
        word = s;
        int ret = 0;
        for(int i = 0; i < s.length(); i++){
            ret+=count(i);
        }
        return ret;
    }
    
    private int count(int i){
        int count = 1, left = i-1, right = i+1;

        while(left >= 0 && right < word.length() && word.charAt(left) == word.charAt(right)){
            count++;
            left--;
            right++;
        }
        
        left = i;
        right = i+1;
        
        while(left >= 0 && right < word.length() && word.charAt(left) == word.charAt(right)){
            count++;
            left--;
            right++;
        }
        return count;
    }
}

Posted 2022-04-24Updated 2022-06-08LeetCode / Medium / 复习8 minutes read (About 1136 words)

5. Longest Palindromic Substring

Question

Given a string s, return the longest palindromic substring in s.

Solution

马拉车算法，专门用于计算最大回文子字符串长度。

预处理

首先需要对字符串进行预处理，将每两个字符之间（包括两端）加上一个符号’#’。
然后在字符串的前后加入任意两个不同的符号。（防止中心扩展时继续搜索）

这个操作使得偶数项的回文字符串变为奇数项的回文字符串，便于接下来进行统一的中心扩展操作。

Manacher算法

参考资料：一文让你彻底明白马拉车算法

用一个数组p[]记录处理后字符串位置的中心展开长度。

初始化一个回文中心的下标位置i，和当前回文中心的右侧范围r。
在进行算法时维护这两个参数。

遍历字符串中除了首尾两个字符以外的位置。

初始化i位置关于c的镜像位置m为2*c-i。
由于回文字符串的对称特性，此时p[i]的中心拓展长度应等于p[m]。
有几种特例情况，p[i]不等于p[m]：

如果p[m] + m的和大于r，则以m为中心扩展的范围超过当前c的中心扩展范围的右界。
此时p[i]无法保证等于p[m]。但是可以确保p[i]至少可以扩展到r，因此将p[i]更新为r-i。
如果i的位置等于r，则可扩展距离为0。
如果m的位置为原字符串的左边界，则此时将p[i]赋值为1是不正确的。
因为p[m]的计算是遇到了边界停止的，而p[i]则没有遇到边界，接下来对i位置从i+p[i]与i-p[i]开始继续进行中心扩展即可。

中心扩展

奇数项的回文字符串由中心扩展，只需要保证i+p[i]+1与i-p[i]-1（两个位置分别表示当前中心扩展的边缘再前进1）的字符相同，则可以继续向下扩展，将p[i]++。

c与r的更新

由于要保证i在r的范围之内，当从i出发的中心扩展范围大于c的中心扩展范围r，需要更新c与r。

时间复杂度

在进行扩展时，每次访问过的位置不会进入中心扩展算法。（比较从中心扩展的边缘开始，即i+p[i]+1与i-p[i]-1）
因此总的时间复杂度为O(n)。

Code

class Solution {
    int n;
    int[] p;
    String newString;
    public String longestPalindrome(String s) {
        n = s.length();
        StringBuffer sb = new StringBuffer();
        if(n == 0) {   //对字符串进行处理
            sb.append("^$");
        }
        else{
            sb.append("^");
            for(int i = 0; i < s.length(); i++){
                sb.append('#');
                sb.append(s.charAt(i));
            }
            sb.append("#$");
        }
        p = new int[sb.length()];
        newString = sb.toString();
        manacher();
        
        int c = 0;
        for(int i = 0; i < sb.length(); i++){
            if(p[i] > p[c]) c = i;
        }
        return s.substring( (c-p[c])/2, (c-p[c])/2+p[c] );
    }
    
    private void manacher(){
        int c = 0, r = 0;
        for(int i = 1; i < p.length - 1; i++){
            int m = 2 * c - i;
            if(i < r){  //当i在r的范围内时，p[i]的值与p[m]相等。
                p[i] = Math.min(r-i, p[m]); //当p[m] + i超过了r时(当前中心拓展边界)，p[i]至少可以取值到r-i
            }
            else{
                p[i] = 0; //当i等于r时，该位置拓展距离为0
            }
            
            while (newString.charAt(i+p[i]+1) == newString.charAt(i-p[i]-1)) {  //中心拓展算法，当两个位置相等时则可拓展距离+1
                p[i]++;
            }
            
            if(i + p[i] > r){   //当当前位置的右侧边界大于现有边界时，更新位置r
                c = i;
                r = i + p[i]; //新的右侧边界为新的中心+拓展长度p[i]
            }
        }
    }
}

Solution 2

getLength方法，计算每一个字符位置的回文长度。（将left填成i+1，right填成i则可以搜索偶数回文的长度。）
如果出现更长的回文，则根据返回的长度，和当前的i计算出字符串的范围。

Code

class Solution {
    public String longestPalindrome(String s) {
        int best = 0;
        int left = 0;
        int right = 0;
        for(int i = 0; i < s.length(); i++){
            int length = Math.max(getLength(s,i,i), getLength(s,i+1,i));
            if(best < length){
                left = i-((length-1)/2-1);
                right = i+(length/2);
                best = length;
            }
        }
        return s.substring(left,right);
    }
    
    private int getLength(String s, int left, int right){
        while(left >= 0 && right < s.length() && left < s.length()){
            if(s.charAt(left) == s.charAt(right)){
                left--;
                right++;
            }
            else break;
        }

        return right - left + 1;
    }
}

Question

Solution

Code

Solution 2

Code

Question

Solution

预处理

Manacher算法

中心扩展

c与r的更新

时间复杂度

Code

Solution 2

Code

Recents

Archives

Links