O(n)的回文子串Manacher算法

待我称王封你为后i 2022-07-26 11:15 160阅读 0赞

O(n)的回文子串Manacher算法

算法代码实现如下：

**样例输入：**

abab
    bbbb
    abba

**样例输出：**

3
    4
    4

#include <stdio.h>
     
    void Manacher (char str[], int len, int Radix[]){
        int mx = 0;    //记录被影响到的最远的位置
        int id = 0;    //最长影响串的位置
        Radix[0] = 0;
        int i;
        for (i=1; i<len; ++i){
            Radix[i] = 1;
            if (mx > i){
                Radix[i] = Radix[2 * id - i];
                if (mx - i < Radix[i])
                    Radix[i] = mx - i;
            }
            while (str[i - Radix[i]] == str[i + Radix[i]])
                ++Radix[i];
            if (i + Radix[i] > mx){
                mx = i + Radix[i];
                id = i;
            }
        }
    }
     
    int Preproccess (char str[], char old_str[]){
        int index;
        int len;
        char middle = '#';
        str[0] = '$';
        str[1] = middle;
        index = 0;
        len = 2;
        while (old_str[index]){
            str[len++] = old_str[index++];
            str[len++] = middle;
        }
        str[len] = '?';
        return len;
    }
     
    int main(void){
        char old_str[200001];
        char str[400004];
        int Radix[400004];
        int len;
        int i;
        int ans;
     
        while (scanf ("%s", old_str) != EOF){
             len = Preproccess (str, old_str);
             Manacher (str, len, Radix);
             ans = 0;
             for (i=1; i<len; ++i){
                if (ans < Radix[i])
                    ans = Radix[i];
             }
             printf ("%d\n", ans - 1);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，160人围观）

还没有评论，来说两句吧...

相关阅读

相关 poj3974 manacher算法,最大回文子串

Sample Input abcbabcbabcba abacacbaaaab END Sample Output Case 1: 13

淩亂°似流年/ 2024年02月17日 22:19/ 0 赞/ 46 阅读

相关最长回文(manacher算法,最大回文子串)

Problem Description 给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度. 回文就是正反读都是一样的字符串,如aba,

刺骨的言语ヽ痛彻心扉/ 2024年02月17日 19:27/ 0 赞/ 42 阅读

相关 hihoCoder#1032 : 最长回文子串(manacher算法)

参考http://blog.csdn.net/xingyeyongheng/article/details/9310555 include<iostream>

╰+攻爆jí腚メ/ 2022年08月21日 00:05/ 0 赞/ 215 阅读

相关 O(n)的回文子串Manacher算法

O(n)的回文子串Manacher算法算法代码实现如下：样例输入： abab bbbb abba 样例输出： 3 4

待我称王封你为后i/ 2022年07月26日 11:15/ 0 赞/ 161 阅读

相关最长回文串——manacher算法java实现

最长回文串是一个很好玩的话题，给出一个无序的不定长的字符序列，如何知道里面的最长回文串呢？ manacher算法的思想是 1 把偶数、奇数长的字符序列变成奇数长度 2 创

我会带着你远行/ 2022年06月10日 03:23/ 0 赞/ 258 阅读

相关【模板——ing】O(n)回文子串（Manacher）算法

1.模板适应问题：（1）：输入串st，求出串st中最长回文子串 2.模板代码： include <cstdio> include <cstring>

系统管理员/ 2022年06月07日 02:55/ 0 赞/ 150 阅读

相关 LeetCode-5. 最长回文子串（Manacher）

5. 最长回文子串 [题目描述][Link 1] -------------------- 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最

约定不等于承诺〃/ 2022年05月26日 11:43/ 0 赞/ 210 阅读

相关【3068 HDU】最长回文串（Manacher算法）

题目：[点击打开题目链接][Link 1] 思路：这题要用到回文串匹配的知识点。我们之前遇到这种题传统思想就是分奇数和偶数情况进行暴力，从前往后遍历每一个字符，然后以该字符为

忘是亡心i/ 2022年05月10日 13:26/ 0 赞/ 247 阅读

相关回文子串问题之Manacher算法

写在前面回文子串问题。题目简述 > 时间限制:1000ms > 单点时限:1000ms > 内存限制:256MB > 描述 > 小Hi和小Ho

短命女/ 2022年05月09日 23:22/ 0 赞/ 206 阅读

相关 Manacher算法解决最长回文子串问题-Java版

Manacher算法解决最长回文子串问题最长回文子串问题，就是给定一个字符串，求出字符串中最长回文子串的长度。回文串就是从头到尾遍历和从尾到头遍历是一模一样的。暴

绝地灬酷狼/ 2022年02月01日 16:25/ 0 赞/ 253 阅读