回文子串（Manacher‘s Algorithm马拉车算法）以及回文子序列

2024-02-15 01:10
文章标签 算法 序列 回文 子串 algorithm manacher 拉车

本文主要是介绍回文子串（Manacher‘s Algorithm马拉车算法）以及回文子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言：

我们先了解回文串，顾名思义就是前后翻转都一样，这样的字符串就是回文串，如aba，abba等

判断回文串的方法
  • 方法一：
    • 最简单的方法就是用原来的字符串跟翻转后的字符串进行比较，只要有一对字符不相等，那么就不是回文串。

代码如下：

# include <iostream>
# include <string>
# include <algorithm>
using namespace std;
int main(void)
{string s;cin>>s;string t = s;reverse(t.begin(),t.end());if(t==s) cout<<"Yes"<<endl;else cout<<"No"<<endl;return 0;}
  • 方法二：
    • 利用栈来解决，但是这里要注意奇偶问题，也就是回文串的个数的总数是奇数还是偶数，这里要判断一下。
    • 假设len为字符串的个数，如果（len&1），那么我们就需要往栈中添加前1到len/2个元素，然后弹栈进行检查，假设压栈的最后一个元素的下标为x,那么我们就拿字符串x+2到len的子串进行比较即可（因为x+1这个元素是最中间的，不需要比较）
    • 如果len是偶数，那么我们就需要往栈中添加前1到len/2个元素，然后弹栈进行检查，假设压栈的最后一个元素的下标为x,那么我们就拿字符串x+1到len的子串进行比较即可，举个例子：len为8,那么入栈的就有1到4,然后我们拿4到8进行比较。

代码如下：

# include <iostream>
# include <string>
# include <algorithm>
# include <stack>
using namespace std;
int main(void)
{string s;cin>>s;stack<char> q;int len = s.size();for(int i=0;i<len/2;++i){q.push(s[i]);}int k = len/2;if(len&1) k = len/2 + 1;while(q.size()){if(q.top()!=s[k]){cout<<"No"<<endl;return 0;}q.pop();++k;}cout<<"Yes"<<endl;return 0;}
  • 方法三：
    • 这也是我最喜欢的做法，用双指针（请点击，了解双指针。）来解决，设置两个变量，i 在头，j 在尾，代表下标，然后一前一后进行遍历，只要发现s[i]!=s[j]，我们就认为此字符串不是回文串。（这里不需要判断长度是否为奇偶，因为我们循环的条件为while(i<j)）

代码如下：

# include <iostream>
# include <string>
# include <algorithm>
# include <stack>
using namespace std;
int main(void)
{string s;cin>>s;int i=0,j=s.size()-1;while(i<j){if(s[i]!=s[j]){cout<<"No"<<endl;return 0;}++i,--j;}cout<<"Yes"<<endl;return 0;}
回文子串

概念：具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串，然后此子串顺序遍历与逆序遍历得到的结果是一样的.

判断回文子串的方法：

在这里插入图片描述

  • 方法一：

采用DP求解

1.首先需要理解回文子串的含义:
如果一个字符串前后两端对应的子串不相同,那么该字符串一定不是回文子串。
当首尾两端字符相同时,然后比较d[i + 1][j - 1]是否是回文子串。

2.按照单个字符、两个字符和多个字符等三个条件依次进行判断。得出动态规划方程为 :
a.单个字符: j == i and s[i] == s[j] => dp[i][j] = true;
b.两个字符: j - i == 1 and s[i] == s[j] => dp[i][j] = true;
c.多个字符: j - i > 1 and dp[i][j] = dp[i + 1][j - 1] and s[i] == s[j]

代码如下：

class Solution {
public:int countSubstrings(string s) {int dp[1010][1010]={0};int ans = 0;for(int i=0;i<s.size();++i){for(int j=0;j<=i;++j){int st  = 0;if(i==j && s[i]==s[j])dp[j][i]=1;else if(j+1==i && s[i]==s[j])dp[j][i] =1;else if(i-j>=2 && s[i]==s[j] &&  dp[j+1][i-1])dp[j][i] = 1;else st = 1;if(!st) ++ans;}}return ans;}
};
  • 方法二:

采用中心扩展法，简单来讲:

就是 把字符串中的 一个或者相邻两个字符 当作中心，
然后通过两个指针 分别向左向右 扩展，并在扩展的过程中记录当前时刻是否具有 回文属性
（注意：必须把 当前元素为中心元素 和 当前元素与后一个元素同为中心元素 两种情况都考虑到）

class Solution {
public:int func(string& s,int l,int r){int ans = 0;while(l>=0 && r<s.size() && s[l]==s[r]){--l;++r;++ans;}return  ans;}int countSubstrings(string s) {int ans = 0;for(int i=0;i<s.size();++i){ans+=func(s,i,i);ans+=func(s,i,i+1);}return ans;}
};
  • 方法三：
    采用马拉车（Manacher’s Algorithm）算法，在下文会详细说到，建议先看完下面的详解再倒回来看代码。
class Solution {
public:int countSubstrings(string s) {string t="$#";for(auto &i:s){t.push_back(i);t.push_back('#');}t+='^';int n = s.size();int ans = 0;vector<int> q(t.size(),0);int right = 0,mi = 0;for(int i=1;i<t.size()-1;++i){q[i] = right>i ? min(q[2*mi-i],right-i) : 1;while(t[i+q[i]]==t[i-q[i]])  ++q[i];if(i>right){mi = i;right = i;}ans+=q[i]/2;}//for(auto i:q) cout<<i<<' ';return ans;}
};

回文子串返回最长子串

在这里插入图片描述

思路：
这道题
但是要特别注意长度为1或者2的情况，具体看代码。

class Solution {
public:bool dp[1010][1010];string longestPalindrome(string s) {int idx=0,idy=0;int ans = 0;int len = s.size();for(int i=0;i<len;++i){   dp[i][i] = 1;}for(int i=len-1;i>=0;--i){for(int j=i;j<len;++j){if(s[i]==s[j]) //这里分为两种情况，要么长度小于等于2，要么就跟dp[i+1][j-1]有关dp[i][j] = j-i<2 ? 1 : dp[i+1][j-1];if(dp[i][j] && ans<j-i+1){ans = j-i+1;idx = i,idy = j;}}}return s.substr(idx,ans);}
};
Manacher‘s Algorithm（马拉车算法）

用来求最长回文子串

我们都知道，在处理回文串的时候要考虑奇偶问题，但是用马拉车算法写就不用考虑这个问题，因为它第一步就是把字符串长度恒改为奇数。

  • 比如"bab"是奇数形式的回文，"naan"就是偶数形式的回文，马拉车算法的第一步是预处理，做法是在每一个字符的左右都加上一个特殊字符，比如加上’#’，那么
  • bab --> #b#a#b#
  • naan --> #n#a#a#n#
  • 这样做的好处是不论原字符串是奇数还是偶数个，处理之后得到的字符串的个数都是奇数个

（一般我们会再在开头和结尾各添加一个不相等的字符，如“@#a#b#c#^”这样）

在马拉车算法中，我们格外要弄懂一件事，那就是p[ ]数组的含义，p[i]表示以字符串S[ i ]字符为中心的回文子串的半径，表示以字符S[ i ]为中心的最长回文字串的最端右字符到T[i]的长度，如以S[ i ]为中心的最长回文子串的为S[ l, r ]，那么P[ i ]=r-i+1。这样最后遍历数组P[ ]，取其中最大值即可。若P[ i ]=1表示该回文串就是T[ i ]本身。

举个例子：
在这里插入图片描述

这里，P[ i ]-1就是该回文子串在原字符串S中的长度 ，那就是P[i]-1就是该回文子串在原字符串S中的长度。

证明：

  • 因为我们改造后的字符串是原来长度的两倍+1，增加了len+1个‘#’字符，那么对于以T[i]为中心的最长回文字串，其长度就为2*P[i]-1,

  • T中所有的回文子串，其中分隔符‘#’的数量一定比其他字符的数量多1，也就是有P[i]个分隔符，那么可想而知剩下P[i]-1个字符来自原字符串

难点就是怎么求P[ ]数组

从左往右计算数组P[ ]， 我们用变量Mi为之前取得最大回文串的中心位置，而变量R是最大回文串能到达的最右端的值。

  • 当 i <=R时，如何计算 P[ i ]的值了？毫无疑问的是数组P中点 i 之前点对应的值都已经计算出来了。利用回文串的特性，我们找到点 i 关于 Mi 的对称点 j ，其值为 j= 2*Mi-i 。因，点 j 、i 在以Mi 为中心的最大回文串的范围内（[L ,R]）

    • a）那么如果P[j] <R-i （同样是L和j 之间的距离），说明，以点 j 为中心的回文串没有超出范围[L ,R]，由回文串的特性可知，从左右两端向Mi遍历，两端对应的字符都是相等的。所以P[ j ]=P[ i ]（这里得先从点j转到点i 的情况），如下图：
      在这里插入图片描述

    • b)如果P[ j ]>=R-i （即 j 为中心的回文串的最左端超过 L），如下图所示。即，以点 j为中心的最大回文串的范围已经超出了范围[L ,R] ，这种情况，等式P[ j ]=P[ i ]还成立吗？显然不总是成立的！因，以点 j 为中心的回文串的最左端超过L，那么在[ L, j ]之间的字符肯定能在( j, Mi ]找到相等的，由回文串的特性可知，P[ i ] 至少等于R- i，至于是否大于R-i（图中红色的部分），我们还要从R+1开始一一的匹配，直达失配为止，从而更新R和对应的Mi以及P[ i ]。
      在这里插入图片描述

  • 2）当 i > R时，如下图。这种情况，没法利用到回文串的特性，只能老老实实的一步步去匹配。
    在这里插入图片描述

string Manacher(string s)
{/*改造字符串*/string res="$#";for(int i=0;i<s.size();++i){res+=s[i];res+="#";}res=res+"^";/*数组*/vector<int> P(res.size(),0);int mi=0,right=0;   //mi为最大回文串对应的中心点，right为该回文串能达到的最右端的值int maxLen=0,maxPoint=0;    //maxLen为最大回文串的长度，maxPoint为记录中心点for(int i=1;i<res.size()-1;++i){P[i]=right>i ?min(P[2*mi-i],right-i):1;     //关键句，文中对这句以详细讲解while(res[i+P[i]]==res[i-P[i]])++P[i];if(right<i+P[i])    //超过之前的最右端，则改变中心点和对应的最右端{right=i+P[i];mi=i;}if(maxLen<P[i])     //更新最大回文串的长度，并记下此时的点{maxLen=P[i];maxPoint=i;}}return s.substr((maxPoint-maxLen)/2,maxLen-1);
}

最长回文子序列

在这里插入图片描述
思路：首先定个dp数组，其含义是在子串s[i…j]中，最长回文子序列的长度为dp[i][j].
那么我们就可以分情况讨论，当s[i]==s[j]时，则dp[i][j] = dp[i+1][j-1]+2；若不相等，那么其长度一定是在（i+1，j）或者（i，j-1）这两个区间选择。
所有dp问题，一定要记得是否需要对数组进行初始化，这个很重要！
这里需要dp[x][x]进行全部赋值为1,因为s[x] == s[x]这是必然的！还有当i>j时，dp[i][j]应该赋值为0;
在这里插入图片描述

class Solution {
public:int longestPalindromeSubseq(string s) {int n = s.size();vector<vector<int> > dp(n,vector<int>(n,0));for(int i=0;i<n;++i){dp[i][i] = 1;}for(int i=n-1;i>=0;--i){for(int j=i+1;j<n;++j){if(s[i]==s[j]){dp[i][j] = dp[i+1][j-1]+2;}else{dp[i][j] = max(dp[i+1][j],dp[i][j-1]);}}}return dp[0][n-1];}
};

第二种做法是利用最长公共子序列来解决。（这个方法比较低效）

这篇关于回文子串（Manacher‘s Algorithm马拉车算法）以及回文子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/710071。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj2406（连续重复子串）

poj2406（连续重复子串）

题意:判断串s是不是str^n，求str的最大长度。 解题思路：kmp可解，后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后，自动跳转到next[i]，所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下； #include<iostream>#include<algorithm>#include<stdio.h>#include<math.
阅读更多...
poj3261（可重复k次的最长子串）

poj3261（可重复k次的最长子串）

题意：可重复k次的最长子串 解题思路：求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N，但实际复杂度很低。题目数据也比较水，不然估计过不了。 代码入下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring
阅读更多...
spoj705( 求不相同的子串个数)

spoj705( 求不相同的子串个数)

题意：求串s的不同子串的个数 解题思路：任何子串都是某个后缀的前缀，对n个后缀排序，求某个后缀的前缀的个数，减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin
阅读更多...
csu1328（近似回文串）

csu1328（近似回文串）

题意：求近似回文串的最大长度，串长度为1000。 解题思路：以某点为中心，向左右两边扩展，注意奇偶分开讨论，暴力解即可。时间复杂度O(n^2); 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>#include<string>#inclu
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2