首页 > 试题广场 >

Manacher算法

[编程题]Manacher算法
  • 热度指数:1092 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个字符串str, 返回str中最长回文子串的长度
[举例]
str=“123”。其中的最长回文子串“1”或者“2”或者“3”,所以返回1。
str=“abc1234321ab”。其中的最长回文子串“1234321”,所以返回7。
[要求]
如果str的长度为N,解决原问题的时间复杂度都达到O(N).

输入描述:
输入为一个字符串str


输出描述:
输出一个整数表示最长回文子串的长度
示例1

输入

123

输出

1
示例2

输入

abc1234321ab

输出

7

备注:
设N表示输入字符串的长度
保证输入字符中只含有小写字母及数字
题目叫Manacher算法,那就老老实实写个Manacher算法来求解
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        char[] str = preprocessing(s.toCharArray());     // 预处理原始字符串,往每个字符之间加#
        int[] radius = new int[str.length];
        int R = -1, C = -1;       // 最远右边界(下一位置)及其对应的中心位置
        int max = 1;
        for(int i = 0; i < str.length; i++){
            radius[i] = i < R? Math.min(radius[2*C - i], R - i): 1;      // i在R内部或不在R内部的情况下,不需要检查的范围
            while(i + radius[i] < str.length && i - radius[i] >= 0){     // 没有越界
                if(str[i + radius[i]] == str[i - radius[i]]){
                    // 往外扩成功了半径就增加
                    radius[i] ++;
                }else{
                    break;
                }
            }
            // 最远右边界变大时要更新其位置和中心
            if(i + radius[i] > R){
                R = i + radius[i];
                C = i;
            }
            max = Math.max(max, radius[i]);
        }
        System.out.println(max - 1);
    }
    
    private static char[] preprocessing(char[] str) {
        StringBuilder sb = new StringBuilder();
        for(char c: str) sb.append("#").append(c);
        sb.append("#");
        return sb.toString().toCharArray();
    }
}

发表于 2021-11-17 21:28:27 回复(0)
def Manacher(long_str):
    # 插入特殊字符#
    long_str_list = list(long_str)
    long_str = '#' + '#'.join(long_str_list) + '#'
    len_long_str = len(long_str)
    R = -1
    C = -1
    _max_radius = 1
    _max_C = 0
    
    radius = [0] * len_long_str
    
    for idx in range(len(long_str)):
        radius[idx] = max(min(radius[2 * C - idx], R - idx), 1) if idx < R else 1
        while(idx + radius[idx] < len_long_str and idx - radius[idx] >= 0):
            if (long_str[idx + radius[idx]] == long_str[idx - radius[idx]]):
                radius[idx] += 1
            else:
                break
        if idx + radius[idx] > R:
            R = idx + radius[idx]
            C = idx
        if _max_radius < radius[idx]:
            _max_radius = radius[idx]
            _max_C = idx
        
    return long_str[_max_C - _max_radius + 1: _max_C + _max_radius].replace('#','')

password = input()
print(len(Manacher(password)))

发表于 2022-06-29 09:27:28 回复(0)
import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        char[] mArr = getMArr(s);
        System.out.println(Manacher(mArr));
    }
    
    public static char[] getMArr(String s) {
        char[] str = s.toCharArray();
        char[] res = new char[2*str.length+1];
        for (int i = 0; i < res.length; i++) {
            if (i % 2 == 0) {
                res[i] = '#';
            }
            else {
                res[i] = str[i/2];
            }
        }
        return res;
    }
    
    public static int Manacher(char[] str) {
        //记录回文子串的半径的数组
        int[] pArr = new int[str.length];
        //记录回文结构可以到达的最右index的下一位置
        int R = -1;
        //记录最大回文结构的中心
        int c = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < str.length; i++) {
            //设置初始回文结构,此情况下为i'回文范围要么在L~R内部,要么超出L
            pArr[i] = R > i ? Math.min(R-i, pArr[2*c-i]) : 1;
            //当以i为中心检测的回文范围没有超出整个数组时
            while (i + pArr[i] < str.length && i - pArr[i] > -1) {
                //对应此时的i在R外或者i'回文范围正好落在L上
                if (str[i + pArr[i]] == str[i - pArr[i]])
                    //因为记录的是半径长度,只需要+1即可
                    pArr[i]++;
                else
                    //若已经实现最大回文结构,则根本不会更新
                    break;
            }
            //更新相关信息
            if(i + pArr[i] > R) {
                R = i + pArr[i];
                c = i;
            }
            max = Math.max(max, pArr[i]);
        }
        return max - 1;
    }
}

发表于 2021-07-19 14:14:48 回复(0)
#include <iostream>
#include <string>
#include <vector>
#include <limits.h>
using namespace std;

string fillStr(string s){
    string str(s.size() * 2 + 1, '#');
    for(int i = 0; i < s.size(); i++){
        str[i * 2 + 1] = s[i];
    }
    return str;
}

int manacher(string s){
    string str = fillStr(s);
    //最右端端点[开区间] 中心 半径vector
    int R = -1;
    int C = -1;
    vector<int> pArr(str.size(), 0);
    int maxVal = INT_MIN;
    for(int i = 0; i < str.size(); i++){
        pArr[i] = i < R ? min(pArr[2 * C - i], R - i) : 1;
        while(i + pArr[i] < str.size() && i - pArr[i] > -1){
            if(str[i + pArr[i]] == str[i - pArr[i]])
                pArr[i]++;
            else
                break;
        }
        if(i + pArr[i] > R){
            R = i + pArr[i];
            C = i;
        }
        maxVal = max(maxVal, pArr[i]);
    }
    return maxVal - 1;
}

int main(void){
    string s;
    cin >> s;
    cout << manacher(s) << endl;
    return 0;
}
个人解题思路如下:
马拉车算法
step1: 扩充字符串s为str(用#)
step2:对字符串中每个字符进行暴力扩展,找到最大回文个数
该字符对应最大回文最右端点开区间
1. i > R 已知区间1
2. pArr[2 * C - i]  < R - i; 则已知回文区间为pArr[2 * C - i];
3.pArr[2 * C - i] > R - i,则已知回文权健为 R - i;
4.pArr[2 * C - i] == R - i,则已知回文区间为R - i 或 pArr[2 *C - i]
并从这基础上进行暴力扩展,如果当前最右端超过R,则更新C和R;
C为中心点
为什么使用前开后闭区间?原因:[L, R) 则区间内元素个数 R - L
判断是否在这个范围内? i + x > R则超过范围

个人出错忘了判断区域
while(i + pArr[i] < str.size() && i - pArr[i] > -1)
发表于 2021-05-28 10:46:42 回复(0)
#include<cstdio>
(802)#include<cstring>
bool ishuiwen(char str[],int l,int r){
    int k=0;
    for(int i=l;i<=(l+r)/2;i++){
        if(str[i]!=str[r-k])
            return false;
        k++;
    }
    return true;
}
int main(){
    char str[500010];
    int maxlen;
    while(scanf("%s",str)!=EOF){
        int len=strlen(str);
        maxlen=1;
        for(int i=0;i<len-maxlen;++i){
            for(int j=i+maxlen;j<len;++j){
                if(ishuiwen(str,i,j))
                {
                    maxlen=j-i+1;
                }
            }
        }
        printf("%d\n",maxlen);
    }
    return 0;
}

发表于 2020-03-25 15:21:12 回复(0)