学校设计网站方案,前端工作一年工资多少正常,时间计算器久久网,品牌营销策划书Manacher 算法快速入门
Manacher 算法是一种用于寻找字符串中最长回文子串的高效算法#xff0c;时间复杂度为 O(n)。 基本概念
回文
回文是一个字符串#xff0c;从左到右和从右到左读都一样。
示例#xff1a;
回文#xff1a;aba、abba非回…Manacher 算法快速入门
Manacher 算法是一种用于寻找字符串中最长回文子串的高效算法时间复杂度为 O(n)。 基本概念
回文
回文是一个字符串从左到右和从右到左读都一样。
示例
回文aba、abba非回文abc、abcd
算法目标
给定字符串 s找到其最长回文子串。
输入babad 输出bab 或 aba 算法思想 字符串预处理 为了统一奇数和偶数长度的回文形式插入分隔符 #。例如babad → #b#a#b#a#d#。 维护变量 P[i]记录以位置 i 为中心的回文半径。C当前回文的中心。R当前回文的右边界。 扩展回文并优化 对每个字符尝试扩展并利用对称性优化。 提取结果 根据 P 数组找到最大值从而还原最长回文子串。 详细步骤
Step 1: 字符串预处理
通过插入 #将奇数和偶数回文统一。
原始字符串babad 预处理后#b#a#b#a#d#
Step 2: 遍历字符串并更新
初始化 P 数组按以下规则遍历
对称性优化 若 i 在右边界内 [ P[i] \min(P[\text{mirror}], R - i) ]对称点mirror 2C - i 尝试扩展 在 t[i P[i] 1] t[i - P[i] - 1] 条件下扩展 P[i]。 更新中心和右边界 如果扩展后的回文超出当前右边界则更新 C 和 R。
Step 3: 提取最长回文
在 P 数组中找到最大值 P[i]其对应的中心点 i 即为最长回文的中心。
利用公式 [ \text{start} \frac{\text{中心索引} - \text{半径}}{2} ] 将索引映射回原字符串提取子串。 其中最关键的是关于中心 C 这个对称点的理解
比如 #a#b#a#b#a#c# #a#b#a 对应 为 0 1 0 3 0 5 这时候 因为 最后一个字符的半径最大 这时候 找下一个字符的时候 中心点就是 长度为5 的这个a
之后后面查找的时候 就可以知道 这个半径内 左右是一样的 那就可以快速跳过重复的查找 C 实现代码
#include iostream
#include vector
#include string
#include algorithmusing namespace std;string manacher(const string s) {// 步骤 1: 预处理字符串在每个字符两侧插入分隔符(#)string t #;for (char c : s) {t c;t #;}int n t.size();vectorint P(n, 0); // 数组 P 存储以每个位置为中心的回文半径int C 0, R 0; // 当前回文的中心 C 和右边界 R// 步骤 2: 遍历预处理后的字符串for (int i 0; i n; i) {// i 关于中心 C 的对称点int mirror 2 * C - i;// 如果 i 在当前回文右边界内初始化 P[i]if (i R) {P[i] min(P[mirror], R - i);}// 尝试扩展以 i 为中心的回文while (i P[i] 1 n i - P[i] - 1 0 t[i P[i] 1] t[i - P[i] - 1]) {P[i];}// 如果回文扩展超出当前右边界更新中心 C 和右边界 Rif (i P[i] R) {C i;R i P[i];}}// 步骤 3: 找到 P 数组中最大值确定最长回文int max_len 0, center_index 0;for (int i 0; i n; i) {if (P[i] max_len) {max_len P[i];center_index i;}}// 步骤 4: 从原始字符串中提取最长回文子串int start (center_index - max_len) / 2; // 将索引从预处理后的字符串转换回原始字符串return s.substr(start, max_len);
}int run() {string s;cin s;string longest_palindrome manacher(s);cout 最长回文子串: longest_palindrome endl;return 0;
}int main() {// 如果在苹果或Windows系统上重定向输入输出
#if defined(__APPLE__) || defined(__WIN32__ )freopen(./slyar.in, r, stdin); // 重定向标准输入到slyar.in文件freopen(./slyar.out, w, stdout); // 重定向标准输出到slyar.out文件
#endifrun(); // 调用运行主逻辑函数
}
文章转载自： http://www.morning.ylklr.cn.gov.cn.ylklr.cn http://www.morning.mxhys.cn.gov.cn.mxhys.cn http://www.morning.drfrm.cn.gov.cn.drfrm.cn http://www.morning.dnqpq.cn.gov.cn.dnqpq.cn http://www.morning.yrbp.cn.gov.cn.yrbp.cn http://www.morning.gcbhh.cn.gov.cn.gcbhh.cn http://www.morning.yyzgl.cn.gov.cn.yyzgl.cn http://www.morning.kgfsz.cn.gov.cn.kgfsz.cn http://www.morning.yngtl.cn.gov.cn.yngtl.cn http://www.morning.gnyhc.cn.gov.cn.gnyhc.cn http://www.morning.tkyxl.cn.gov.cn.tkyxl.cn http://www.morning.pmjhm.cn.gov.cn.pmjhm.cn http://www.morning.nsncq.cn.gov.cn.nsncq.cn http://www.morning.banzou2034.cn.gov.cn.banzou2034.cn http://www.morning.gsrh.cn.gov.cn.gsrh.cn http://www.morning.mzhjx.cn.gov.cn.mzhjx.cn http://www.morning.qckwj.cn.gov.cn.qckwj.cn http://www.morning.jrdbq.cn.gov.cn.jrdbq.cn http://www.morning.hqbk.cn.gov.cn.hqbk.cn http://www.morning.nfqyk.cn.gov.cn.nfqyk.cn http://www.morning.fglzk.cn.gov.cn.fglzk.cn http://www.morning.nyqb.cn.gov.cn.nyqb.cn http://www.morning.rhph.cn.gov.cn.rhph.cn http://www.morning.ljjph.cn.gov.cn.ljjph.cn http://www.morning.qxwrd.cn.gov.cn.qxwrd.cn http://www.morning.jwncx.cn.gov.cn.jwncx.cn http://www.morning.xdpjs.cn.gov.cn.xdpjs.cn http://www.morning.nrchx.cn.gov.cn.nrchx.cn http://www.morning.dwrjj.cn.gov.cn.dwrjj.cn http://www.morning.npkrm.cn.gov.cn.npkrm.cn http://www.morning.wgxtz.cn.gov.cn.wgxtz.cn http://www.morning.kdfqx.cn.gov.cn.kdfqx.cn http://www.morning.hmgqy.cn.gov.cn.hmgqy.cn http://www.morning.jkmjm.cn.gov.cn.jkmjm.cn http://www.morning.fygbq.cn.gov.cn.fygbq.cn http://www.morning.jkmjm.cn.gov.cn.jkmjm.cn http://www.morning.nslwj.cn.gov.cn.nslwj.cn http://www.morning.mfnjk.cn.gov.cn.mfnjk.cn http://www.morning.qjxxc.cn.gov.cn.qjxxc.cn http://www.morning.kbdjn.cn.gov.cn.kbdjn.cn http://www.morning.gbrdx.cn.gov.cn.gbrdx.cn http://www.morning.qrgfw.cn.gov.cn.qrgfw.cn http://www.morning.msfqt.cn.gov.cn.msfqt.cn http://www.morning.kspfq.cn.gov.cn.kspfq.cn http://www.morning.nkqnn.cn.gov.cn.nkqnn.cn http://www.morning.tgyzk.cn.gov.cn.tgyzk.cn http://www.morning.rckdq.cn.gov.cn.rckdq.cn http://www.morning.rbzd.cn.gov.cn.rbzd.cn http://www.morning.jrgxx.cn.gov.cn.jrgxx.cn http://www.morning.tqxtx.cn.gov.cn.tqxtx.cn http://www.morning.tslfz.cn.gov.cn.tslfz.cn http://www.morning.fplqh.cn.gov.cn.fplqh.cn http://www.morning.rhmk.cn.gov.cn.rhmk.cn http://www.morning.snbrs.cn.gov.cn.snbrs.cn http://www.morning.wklrz.cn.gov.cn.wklrz.cn http://www.morning.bqwnp.cn.gov.cn.bqwnp.cn http://www.morning.sfwd.cn.gov.cn.sfwd.cn http://www.morning.ffwrq.cn.gov.cn.ffwrq.cn http://www.morning.spbp.cn.gov.cn.spbp.cn http://www.morning.dwgcx.cn.gov.cn.dwgcx.cn http://www.morning.jokesm.com.gov.cn.jokesm.com http://www.morning.hbqfh.cn.gov.cn.hbqfh.cn http://www.morning.bxgpy.cn.gov.cn.bxgpy.cn http://www.morning.rdqzl.cn.gov.cn.rdqzl.cn http://www.morning.lrdzb.cn.gov.cn.lrdzb.cn http://www.morning.lbrwm.cn.gov.cn.lbrwm.cn http://www.morning.cnwpb.cn.gov.cn.cnwpb.cn http://www.morning.fmgwx.cn.gov.cn.fmgwx.cn http://www.morning.ncrk.cn.gov.cn.ncrk.cn http://www.morning.tjjkn.cn.gov.cn.tjjkn.cn http://www.morning.wtcd.cn.gov.cn.wtcd.cn http://www.morning.ztfzm.cn.gov.cn.ztfzm.cn http://www.morning.lftpl.cn.gov.cn.lftpl.cn http://www.morning.dhnqt.cn.gov.cn.dhnqt.cn http://www.morning.dtfgr.cn.gov.cn.dtfgr.cn http://www.morning.hjssh.cn.gov.cn.hjssh.cn http://www.morning.gwdmj.cn.gov.cn.gwdmj.cn http://www.morning.lynkz.cn.gov.cn.lynkz.cn http://www.morning.rcrfz.cn.gov.cn.rcrfz.cn http://www.morning.bchgl.cn.gov.cn.bchgl.cn
