当前位置: 首页 > news >正文

马拉车算法(C/C++)

#1024程序员节 | 征文#

马拉车算法(Manacher's Algorithm)是一种用于在字符串中查找最长回文子串的线性时间复杂度算法。该算法由Udi Manacher在1980年代提出,因此得名。它的核心思想是利用已知的回文信息来减少不必要的比较,从而提高效率。

算法步骤

  1. 预处理字符串: 为了处理奇数长度和偶数长度的回文串,算法首先对输入字符串进行预处理。在每个字符之间插入一个特殊字符(通常是#),并在字符串的开头和结尾也各插入一个。这样做的目的是为了让每个字符都有一个唯一的中心位置。

  2. 初始化变量

    • p[]:一个数组,用于存储每个位置的回文半径。
    • C:当前考虑的中心位置。
    • R:当前考虑的右端点,即以C为中心的回文串的最右端。
  3. 遍历字符串: 对于预处理后的字符串中的每个位置i,算法尝试找到以i为中心的回文串的半径。这个过程分为两步:

    • 利用已知的回文信息:如果i在当前考虑的回文串内(即i < R),则可以利用对称位置的回文半径来减少比较次数。
    • 扩展回文串:如果i不在当前考虑的回文串内,或者需要进一步扩展回文串,算法会尝试扩展以i为中心的回文串,直到无法进一步扩展。
  4. 更新最大回文串: 在遍历过程中,如果找到的回文串半径大于之前记录的最大半径,则更新最大回文串的起始位置和半径。

  5. 提取最长回文子串: 遍历完成后,根据记录的最大半径和起始位置,从原始字符串中提取最长的回文子串。


算法详解

  • 中心扩展思想:马拉车算法利用了中心扩展的思想,即以每个字符为中心,向两边扩展,直到无法形成回文串为止。这种方法可以避免重复比较相同的字符对。

  • 利用对称性:算法利用了回文串的对称性,即如果以i为中心的回文串已知,那么以2*C - i为中心的回文串的半径至少与以C为中心的回文串的半径相同。这里C是当前考虑的中心位置。

  • 动态规划:虽然马拉车算法不是传统意义上的动态规划算法,但它的思想与动态规划类似,即利用之前计算的结果来简化当前的计算。


复杂度分析

  • 时间复杂度:O(n),其中n是输入字符串的长度。这是因为每个位置的回文半径只计算一次。
  • 空间复杂度:O(n),用于存储回文半径的数组。

代码实现:

#include <iostream>
#include <vector>
#include <string>
using namespace std;string manacher(const string& s) {if (s.empty()) return s;// 预处理字符串,插入特殊字符string t = "#";for (char c : s) {t += c;t += "#";}int n = t.length();vector<int> p(n, 0);int C = 0, R = 0; // C为当前回文的中心,R为当前回文的右边界int maxLen = 0, centerIndex = 0;for (int i = 1; i < n; i++) {if (i < R) {int mirror = 2 * C - i;p[i] = min(R - i, p[mirror]);}int left = i - p[i], right = i + p[i];while (left >= 1 && right < n - 1 && t[left - 1] == t[right + 1]) {p[i]++;left--;right++;}if (i + p[i] > R) {C = i;R = i + p[i];}if (p[i] > maxLen) {maxLen = p[i];centerIndex = i;}}// 从预处理的字符串中提取最长回文子串int start = (centerIndex - maxLen) / 2;return s.substr(start, maxLen - 1); // 减1是因为预处理字符串中插入了特殊字符
}int main() {string s;cin >> s;cout << manacher(s) << endl;return 0;
}


应用实例:

在LeetCode上的题目“5. Longest Palindromic Substring”就是一个典型的应用实例,要求找出给定字符串中的最长回文子串。马拉车算法可以应用于生物信息学中DNA序列的回文结构分析,以及文本处理中的回文检测等场景。该算法也可以用于解决其他与回文相关的问题,如找出所有回文子串、判断回文对等。

算法实现部分:
string manacher(string s) {string t = "#";for (char c : s) {t += c;t += "#";}vector<int> p(t.size(), 0);int C = 0, R = 0;int maxLen = 0, centerIndex = 0;for (int i = 1; i < t.size(); i++) {if (i < R) p[i] = min(p[2 * C - i], R - i);else p[i] = 1;while (t[i + p[i]] == t[i - p[i]]) p[i]++;if (i + p[i] > R) {C = i;R = i + p[i];}if (p[i] > maxLen) {maxLen = p[i];centerIndex = i;}}int start = (centerIndex - maxLen) / 2;return s.substr(start, maxLen - 1);
}

马拉车算法是解决最长回文子串问题的有效方法,其线性时间复杂度使其在处理大规模数据时具有明显优势。文章到此为止感谢大家的支持。


http://www.mrgr.cn/news/56447.html

相关文章:

  • 3184. 构成整天的下标对数目 I
  • 车规芯片SOC简介
  • web服务器介绍
  • 图文深入理解Oracle Total Recall
  • 【JavaEE初阶】网络编程TCP协议实现回显服务器以及如何处理多个客户端的响应
  • GJS-WCP
  • [ 钓鱼实战系列-基础篇-5 ] 一篇文章教会你用红队思维设计钓鱼模板(附常见的钓鱼邮件模板)
  • Tcp协议讲解与守护进程
  • Docker基础知识教程(最详细最全)
  • Android 拦截第三方推送的通知消息或系统消息或通知栏
  • 【C++、数据结构】二叉排序树(二叉查找树、二叉搜索树)(图解+完整代码)
  • C++入门知识
  • 【二刷hot100】day 4
  • Python程序设计 内置模块 随机函数
  • 【C++】— 一篇文章让你认识STL
  • Git的原理和使用(六)
  • 开源医疗管理的未来:参与码良诊所管理系统,助力智能医疗
  • 中国古代数学的杰出研究成果之一 - 杨辉三角 - 怎么用go、C++进行编程解决
  • 二叉树展开为链表
  • 代码随想录算法训练营第51天|101. 孤岛的总面积、102. 沉没孤岛、103. 水流问题、104.建造最大岛屿