如何创建属于个人网站,如何建设小说网站并且盈利,网站底部备案图标,logo设计找什么公司回文问题 目录 1、简介2、经典的回文问题(1) 判断一个字符串是否为回文(2) 给定字符集求构建的最长回文长度(3) 求最长回文子串方法一#xff1a;中心拓展方法二#xff1a;Manacher 算法 (4) 求回文子串的数目方法一#xff1a;中心拓展方法二#xff1a;Manacher 算法 1、…回文问题 目录 1、简介2、经典的回文问题(1) 判断一个字符串是否为回文(2) 给定字符集求构建的最长回文长度(3) 求最长回文子串方法一中心拓展方法二Manacher 算法 (4) 求回文子串的数目方法一中心拓展方法二Manacher 算法 1、简介 对于一个给定的字符串如果它的正序和倒序是相同的则称这样的字符串为 回文。
例如对于字符串 “aabaa”它的倒序也为 “aabaa”因此它是一个回文对于字符串 “abba”它的倒序也为 “abba”因此它也是一个回文对于字符串 “abbc”它的倒序为 “cbba”因此它不是一个回文。
从回文的定义可以看出回文总是 关于中心对称 的。 2、经典的回文问题 (1) 判断一个字符串是否为回文
根据回文的定义可以知道回文是一个关于中心对称的字符串。那么要判断一个字符串是否为回文最简单的办法就是定义两个指针 l l l 和 r r r 分别从字符串的首尾向字符串中心进行扫描。在扫描过程中一旦存在两个字符不相同则说明这个字符串是不是回文否则这个扫描过程会一直进行下去直到两个指针相遇在这情况下说明当前字符串是一个回文。
根据这样的思路可以得到判断字符串是否为回文的代码如下
// 判断字符串 s 是否为回文
bool isPalindrome(const string s) {int l 0, r s.length() - 1;while(l r s[l] s[r]){l;r--;}if(l r) return false;else return true;
}复杂度分析
时间复杂度 O ( n ) O(n) O(n)。
空间复杂度 O ( 1 ) O(1) O(1)。 (2) 给定字符集求构建的最长回文长度
给定一个包含大写字母和小写字母的字符串 s s s 返回由这些字符构造的最长的回文长度。例如对于给定的字符串 “abccccdd”能够构建的最长的回文为 “dccaccd”或 “dccbccd” 等其长度为 7。
对应题目LeetCode.409 最长回文串。
分析
这道题乍一看会觉得无从下手但想通之后会发现很简单。
还是从回文的性质出发由于回文是关于中心对称的。因此所有回文总是满足以下两个条件之一
若当前回文长度为偶数则所有字符都将出现偶数次若当前回文长度为奇数则位于中心位置的字符将出现奇数次其余所有字符都将出现偶数次
基于此从贪心的角度出发要使构建的回文长度最长可以把所有出现偶数次的字符都选中。在这基础上如果还有奇数次的字符假设出现次数为 t t t则将这些字符中的 t − 1 t-1 t−1 个偶数次字符也选中并在最后再选择一个出现次数为奇数次的字符位于回文中心。下图展示了该思路的具体执行流程 对应代码
#includeunordered_map
using namespace std;// 给定字符集求构建的最长回文长度
int longestPalindrome(const string s)
{unordered_mapchar, int mp;int slen s.length();int cnt 0, tmp, odd 0;// 统计各字符的出现次数for (int i 0; i slen; i)mp[s[i]];// 遍历字典偶数的字符全部都可用奇数的只能用 - 1 个数的字符for (const auto pair : mp){tmp pair.second;cnt (tmp - (tmp1));// 标记是否存在奇数个数的字符if (tmp 1) odd 1;}return cnt odd;
}复杂度分析
时间复杂度 O ( n ) O(n) O(n)。
空间复杂度 O ( n ) O(n) O(n)。 (3) 求最长回文子串
给定一个字符串 s s s求 s s s 中的最长回文子串。例如对于字符串 “cbbd”其中的最长回文子串为 “bb”对于字符串 “aasabasa”其中的最长回文子串为 “asabasa”。
对应题目LeetCode.5 最长回文子串。
分析
最简单直接的办法就是枚举即枚举所有子串然后依次判断当前子串是否为一个回文如果是就记录当前回文串的长度并维护更新一个用于记录最大回文长度的变量和对应位置。枚举结束时便可以基于维护的相关变量输出最长的回文子串。对于一个字符串 s s s枚举其子串的代码如下
// 双重循环枚举字符串 s 的全部子串
int slen s.length();
for(int l0; lslen; l)for(int rl; rslen; r){string substr s.substr(l, r-l1);/* 判断 substr 是否为回文的代码 */}这个枚举过程是 O ( n 2 ) O(n^2) O(n2) 的时间复杂度。对于每个子串还需要判断其是否为回文 O ( n ) O(n) O(n) 的时间复杂度。因此该方法最终的时间复杂度为 O ( n 3 ) O(n^3) O(n3)是不能容忍的。因此这个方法不可取。
方法一中心拓展
注意到回文是一个对称结构因此我们可以考虑这样的一种枚举方式遍历每个字符串并将其作为回文中心在此基础上再向两侧拓展以寻找当前回文中心的最长边界。在这个过程中每次都维护更新一个用于记录最大回文长度的变量和对应位置遍历结束后便能得到最长的回文子串。在这个枚举方案中遍历原始字符串的时间复杂度为 O ( n ) O(n) O(n)向两侧拓展寻找回文中心的最长边界的时间复杂度也为 O ( n ) O(n) O(n)。因此中心拓展方法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。
具体实现时需要处理一个问题如何有序地枚举所有回文中心之所以有这个问题是因为回文需要分长度为奇数和长度为偶数的两种情况。如果回文长度是奇数那么回文中心是一个字符如果回文长度是偶数那么中心是两个字符。对于某个字符串 “abcbd”它的回文中心有以下两种划分方式
回文中心为单字符即 “a”、“b”、“c”、“b”、“d”亦即原字符串本身的长度 n n n回文中心为双字符即 “ab”、“bc”、“cb”、“bd”亦即原字符串本身的长度再减 1 n − 1 n-1 n−1
因此对长度为 n n n 的字符串 s s s我们需要枚举的回文中心有 n ( n − 1 ) 2 n − 1 n(n-1)2n-1 n(n−1)2n−1 种情况。
中心拓展的思路如下 对应代码
// 给定字符串求最长的回文子串
string longestPalindrome(const string s)
{// longestPd 记录最长的回文子串长度posPd 记录对应最长子串的起始位置int slen s.size(), longestPd 0, posPd;int l, r, lenPd;for (int i 0, maxIter 2 * slen - 1; i maxIter; i){// 确定当前的回文中心l i / 2, r i / 2 (i 1);// 寻找当前回文中心的最长边界while (l 0 r slen s[l] s[r])l--, r;// 计算当前回文的长度lenPd r - l - 1;// 更新if (lenPd longestPd){longestPd lenPd;posPd l 1;}}return s.substr(posPd, longestPd);
}复杂度分析
时间复杂度 O ( n 2 ) O(n^2) O(n2)。
空间复杂度 O ( n ) O(n) O(n)。 方法二Manacher 算法
Manacher 算法是一种在线性时间内求解最长回文子串的算法。
Manacher 算法也会面临「方法一」中的奇数长度和偶数长度的问题它的处理方式是在所有的相邻字符中间以及字符串的首尾位置插入 #比如 “abaa” 会被处理成 “#a#b#a#a#”这样可以保证所有找到的回文串都是奇数长度的亦即所有的回文都是以单字符为中心的。在下面的谈论中我们用 s s s 表示添加了 “#” 的新字符串。
在学习 Manacher 算法之前需要先了解以下定义。
回文半径 RL回文中最左或最右位置的字符与其对称轴之间的字符数量称为回文半径包含对称轴本身我们用 R L RL RL 表示。因此对字符串 s s s 中的某个字符 s [ i ] s[i] s[i] 而言我们可以用数组 R L [ i ] RL[i] RL[i] 表示以字符 s [ i ] s[i] s[i] 为回文中心得到的回文半径。例如对于字符串 “aba” 和字符串 “abba” 有以下定义
位置 0 1 2 3 4 5 6
字符 # a # b # a #
RL 1 2 1 4 1 2 1
RL-1 0 1 0 3 0 1 0位置 0 1 2 3 4 5 6 7 8
字符 # a # b # b # a #
RL 1 2 1 2 5 2 1 2 1
RL-1 0 1 0 1 4 1 0 1 0对字符串 “#a#b#a#” 而言第一个字符 “a” 的回文半径为 2子串 “#a#” 构成一个回文最左侧的 “#” 到 “a” 共计 2 个字符 “#a”因此 R L [ 1 ] 2 RL[1]2 RL[1]2。
对字符串 “#a#b#b#a#” 而言正中间的字符 “#” 的回文半径为 5整个字符串 “#a#b#b#a#” 构成一个回文最左侧的 “#” 到正中间 “a” 共计 5 个字符 “#a#b#”因此 R L [ 4 ] 5 RL[4]5 RL[4]5。
注意到在上面给出的例子中我们还给出了 R L − 1 RL-1 RL−1实际上就是 “最左或最右位置的字符与其对称轴之间的字符数不包含对称轴本身”可以发现各 R L [ i ] − 1 RL[i]-1 RL[i]−1 的值恰好等于在原字符串中以字符 s [ i ] s[i] s[i] 为对称轴的回文长度。例如在字符串 “#a#b#a#” 中 R L [ 3 ] − 1 3 RL[3]-13 RL[3]−13恰好等于原始字符串 “aba” 以字符 b b b 为回文中心得到的最长回文长度。在字符串 “#a#b#b#a#” 中 R L [ 4 ] − 1 4 RL[4]-14 RL[4]−14恰好等于原始字符串 “abba” 以字符 b b bb bb 为回文中心得到的最长回文长度“#” 是插入的字符可以理解为一个虚拟字符。如果处理 R L [ i ] RL[i] RL[i] 时对应的 s [ i ] s[i] s[i] 是虚拟字符它对应在原字符串中的回文中心就是以 s [ i ] s[i] s[i] 前后两个字符组成的双字符。
另一方面由于回文是对称的因此对于任意的 R L [ i ] RL[i] RL[i] 都有这样的一个性质 i − R L [ i ] 1 2 \frac{i-RL[i]1}{2} 2i−RL[i]1以字符 s [ i ] s[i] s[i] 为回文中心构成的最长回文在原字符串中的起始位置。例如在字符串 “#a#b#a#” 中 3 − R L [ 3 ] 1 2 0 \frac{3-RL[3]1}{2}0 23−RL[3]10而在原始字符串 “aba” 中以字符 “b” 为回文中心的起始索引也是 0在字符串 “#a#b#b#a#” 中 4 − R L [ 4 ] 1 2 0 \frac{4-RL[4]1}{2}0 24−RL[4]10而在原始字符串 “abba” 中以字符 “bb” 为回文中心的起始索引也是 0。
在熟悉以上概念后“求最长回文子串” 的任务就被转换为 “求 R L RL RL 数组”。更准确地说是在线性时间复杂度内求 R L RL RL 数组。Manacher 算法计算 R L RL RL 数组的整体流程和中心拓展方法是一致的(1) 遍历字符串 s s s假设遍历指针为 i i i(2) 计算以各字符 s [ i ] s[i] s[i] 为回文中心的回文半径即 R L [ i ] RL[i] RL[i]。与中心拓展方法不同的是Manacher 算法充分利用了回文 中心对称 的特性进而大幅降低了许多重复计算。
最远已访问指针 VisitedPos在计算以字符 s [ i ] s[i] s[i] 为回文中心的回文半径时我们定义 “沿着与遍历方向一致的被访问的最远位置为 V i s i t e d P o s VisitedPos VisitedPos”。这就是说 V i s i t e d P o s VisitedPos VisitedPos 指示了在更新 R L RL RL 数组时被访问到的最远位置。
最远已访问指针对应的回文中心指针 MidPos为便于相关参数的计算还需要定义最远已访问指针 V i s i t e d P o s VisitedPos VisitedPos 对应的回文中心位置 M i d P o s MidPos MidPos显然 M i d P o s ⌊ V i s i t e d P o s 2 ⌋ MidPos\left\lfloor\frac{VisitedPos}{2}\right\rfloor MidPos⌊2VisitedPos⌋。
下图给出了 V i s i t e d P o s VisitedPos VisitedPos 和 M i d P o s MidPos MidPos 的具体更新步骤 关于 V i s i t e d P o s VisitedPos VisitedPos 和 M i d P o s MidPos MidPos需要注意以下两个关键点 V i s i t e d P o s ≥ i VisitedPos \geq i VisitedPos≥i。最远已访问指针 V i s i t e d P o s VisitedPos VisitedPos 始终不小于遍历指针 i i i。 i ≥ M i d P o s i \geq MidPos i≥MidPos。理想情况下每次中心拓展 V i s i t e d P o s VisitedPos VisitedPos 都进行了更新则 i ⌊ V i s i t e d 2 ⌋ M i d P o s i\left\lfloor\frac{Visited}{2}\right\rfloorMidPos i⌊2Visited⌋MidPos其他情况下 V i s i t e d P o s VisitedPos VisitedPos 未被更新则 i i 1 i i1 ii1 而 M i d P o s MidPos MidPos 不发生变化因此有 i M i d P o s iMidPos iMidPos。综上 i ≥ M i d P o s i \geq MidPos i≥MidPos。
下面正式进入核心环节Manacher 算法如何将 R L RL RL 数组的求解降低至线性时间复杂度的。
首先要明确一点由 V i s i t e d P o s VisitedPos VisitedPos 和 M i d P o s MidPos MidPos 共同指示的回文是一个关于 M i d P o s MidPos MidPos 对称的字符串。例如在下图中字符串 s [ l V i s i t e d P o s , M i d P o s ] s[lVisitedPos, MidPos] s[lVisitedPos,MidPos] 和 s [ M i d P o s , r V i s i t e d P o s ] s[MidPos, rVisitedPos] s[MidPos,rVisitedPos] 完全一致。 在这情况下当我们计算以 s [ 13 ] s[13] s[13] 为回文中心的回文半径 R L [ 13 ] RL[13] RL[13] 时就不需要再执行一次中心拓展过程因为 s [ 13 ] s[13] s[13] 和 s [ 7 ] s[7] s[7] 关于 M i d P o s 10 MidPos10 MidPos10 对称而 R L [ 7 ] RL[7] RL[7] 在之前已经计算过了所以可以确定 R L [ 13 ] RL[13] RL[13] 的下限即 R L [ 13 ] ≥ R L [ 7 ] 3 RL[13]\geq RL[7]3 RL[13]≥RL[7]3然后在这基础上再对 R L [ 13 ] RL[13] RL[13] 进行中心拓展。这样一来就大幅降低了计算 R L [ 13 ] RL[13] RL[13] 的开销。注根据对称法则 i i i、 j j j 和 M i d P o s MidPos MidPos 存在关系 i j 2 ∗ M i d P o s ij2*MidPos ij2∗MidPos即 j 2 ∗ M i d P o s − i j2*MidPos-i j2∗MidPos−i。
但是直接取 R L [ 13 ] ≥ R L [ 7 ] RL[13]\geq RL[7] RL[13]≥RL[7] 是不准确的。考虑一种情况以 s [ 7 ] s[7] s[7] 为回文中心的半径长度超过了 l V i s i t e d P o s lVisitedPos lVisitedPos 指示的位置如下图所示。 在这种情况下由于以 M i d P o s MidPos MidPos 为回文中心的回文仅能保证子串 s [ l V i s i t e d P o s , M i d P o s ] s[lVisitedPos, MidPos] s[lVisitedPos,MidPos] 和 s [ M i d P o s , r V i s i t e d P o s ] s[MidPos, rVisitedPos] s[MidPos,rVisitedPos] 一致而无法保证在超出这个范围以外的部分也相同。此时 R L [ i ] RL[i] RL[i] 的下限又该如何确定呢这时候就需要从回文 中心对称 的特性出发进行思考了观察下图 证明字符串 S 3 S_3 S3 和 S 4 S_4 S4 关于 i i i 对称 因为 回文 P a l i n d r o m e 1 Palindrome1 Palindrome1 关于 j j j 对称 所以 字符串 S 1 S_1 S1 和 S 2 S_2 S2 关于 j j j 对称 因为 回文 P a l i n d r o m e 2 Palindrome2 Palindrome2 关于 M i d P o s MidPos MidPos 对称 所以 字符串 S 2 S_2 S2 和 S 3 S_3 S3 关于 M i d P o s MidPos MidPos 对称 由于 S 1 S_1 S1 和 S 2 S_2 S2 关于 j j j 对称 S 2 S_2 S2 和 S 3 S_3 S3 关于 M i d P o s MidPos MidPos 对称 所以 字符串 S 1 S 3 S_1 S_3 S1S3 又因为 回文 P a l i n d r o m e 2 Palindrome2 Palindrome2 关于 M i d P o s MidPos MidPos 对称 所以 字符串 S 1 S_1 S1 和 S 4 S_4 S4 关于 M i d P o s MidPos MidPos 对称 综合 S 1 S 3 S_1 S_3 S1S3 可知 S 3 S_3 S3 和 S 4 S_4 S4 关于 M i d P o s MidPos MidPos 对称 因此当以 s [ j ] s[j] s[j] 为中心的回文范围超出了 l V i s i t e d P o s lVisitedPos lVisitedPos 时我们可以确定字符 s [ i ] s[i] s[i] 的回文半径不低于 V i s i t e d P o s − i 1 VisitedPos-i1 VisitedPos−i1即 R L [ i ] ≥ ( r V i s i t e d P o s − i 1 ) RL[i] \geq (rVisitedPos-i1) RL[i]≥(rVisitedPos−i1)。 综上可以将字符 s [ i ] s[i] s[i] 的回文半径 R L [ i ] RL[i] RL[i] 的初始化归结为以下 3 种情况 i V i s i t e d P o s i VisitedPos iVisitedPos 说明以 i i i 为中心的回文还没有任何一个部分被访问过这种情况下只能从 i i i 的左右两边进行中心扩展即初始化 R L [ i ] 1 RL[i]1 RL[i]1。 i V i s i t e d P o s i VisitedPos iVisitedPos R L [ j ] ≤ ( V i s i t e d P o s − i ) RL[j] \leq (VisitedPos-i) RL[j]≤(VisitedPos−i) 时以 i i i 的对称位置 j j j 为中心的回文未超过 V i s i t e d P o s VisitedPos VisitedPos 对应回文的范围初始化 R L [ i ] R [ j ] RL[i]R[j] RL[i]R[j]。 R L [ j ] ( V i s i t e d P o s − i ) RL[j] (VisitedPos-i) RL[j](VisitedPos−i) 时以 i i i 的对称位置 j j j 为中心的回文超过了 V i s i t e d P o s VisitedPos VisitedPos 对应回文的范围初始化 R L [ i ] V i s i t e d P o s − i RL[i]VisitedPos-i RL[i]VisitedPos−i。
以上便是 Manacher 算法的核心思路在寻找最长的回文子串时还需要额外引入一个变量来记录当前找到的最长回文长度。可能你会疑惑确定了最长回文长度还需要一个变量保存这个回文对应的起点或者中心位置才能得到对应的回文串实际上并不需要。还记得么前面我们曾说过在对原始字符串插入 “#” 后各 R L RL RL 通过 i − R L [ i ] 1 2 \frac{i-RL[i]1}{2} 2i−RL[i]1 便可以得到该回文对应的起点索引。
于是可以写出 Manacher 算法的完整代码如下
string longestPalindromeStr(const string s)
{// 预处理填充 “#”string s_;for (int i 0, slen s.length(); i slen; i){s_ #;s_ s[i];}s_ #;// 寻找最长回文子串int slen s_.size(), visitedPos 0, midPos 0, maxRLPos 0;vectorint RL(slen, 0);for (int i 0; i slen; i){// 当前遍历字符的位置位于 visitedPos 之前if (i visitedPos)RL[i] min(RL[2 * midPos - i], visitedPos - i 1);// 当前遍历字符的位置与 visitedPos 重合elseRL[i] 1;// 中心拓展(注意处理边界)while (i - RL[i] 0 i RL[i] slen s_[i - RL[i]] s_[i RL[i]])RL[i] 1;// 更新 visitedPos 和 midPosif (i RL[i] - 1 visitedPos){visitedPos RL[i];midPos i;}// 更新 maxRLif (RL[i] RL[maxRLPos])maxRLPos i;}return s.substr((maxRLPos - RL[maxRLPos] 1) / 2, RL[maxRLPos] - 1);
}复杂度分析
时间复杂度 O ( n ) O(n) O(n)。
空间复杂度 O ( n ) O(n) O(n)。 (4) 求回文子串的数目
给定一个字符串 s s s求 s s s 中全部的回文子串数目。例如对于字符串 “abc”其中的回文子串有 “a”、“b”、“c” 共 3 个因此返回 3对于字符串 “aba”其中的回文子串有 “a”、“b”、“c” 、“aba” 共 4 个因此返回 4。
对应题目LeetCode.647 回文子串。
分析
方法一中心拓展
可以利用中心拓展方式枚举全部的回文子串并进行统计对应代码如下
int countSubstrings(string s)
{int slen s.size(), count 0;int l, r;for (int i 0, maxIter 2 * slen - 1; i maxIter; i){// 确定当前的回文中心l i / 2, r i / 2 (i 1);// 枚举以当前字符为中心的全部回文while (l 0 r n s[l] s[r]){--l;r;count;}}return count;
}复杂度分析
时间复杂度 O ( n 2 ) O(n^2) O(n2)。
空间复杂度 O ( 1 ) O(1) O(1)。 方法二Manacher 算法
从前面的分析知道 Manacher 算法可以在线性时间复杂度度内求出全部的 R L [ i ] RL[i] RL[i]即所有字符的最长回文半径这实际上就已经枚举了所有的回文。那么要统计给定字符的全部回文子串就只需要在 Manacher 算法内部进行累加即可。
需要注意的是由于对字符串添加了 “#”就需要对这些字符进行排除。如何排除呢
很简单注意到在添加 “#” 后所有的回文都是以单字符为中心的在这种情况下所有原本是双字符为中心的回文对应在新串中为 “#”的最小 R L [ i ] RL[i] RL[i] 为 3所有单字符为中心的回文的最小 R L [ i ] RL[i] RL[i] 也为 3而对于无效的 “#” 符的 R L [ i ] RL[i] RL[i] 值就只能取到 1。因此对所有的 R L [ i ] RL[i] RL[i]其真实贡献可以取 R L [ i ] − 1 2 \frac{RL[i]-1}{2} 2RL[i]−1这样一来就消除了 “#” 对真实结果的影响。
下面给出利用 Manacher 算法求解该问题的完整代码
int countSubstrings(const string s)
{// 预处理填充 “#”string s_;for (int i 0, slen s.length(); i slen; i){s_ #;s_ s[i];}s_ #;// 统计回文子串个数int slen s_.size(), visitedPos 0, midPos 0, count 0;vectorint RL(slen, 0);for (int i 0; i slen; i){// 当前遍历字符的位置位于 visitedPos 之前if (i visitedPos)RL[i] min(RL[2 * midPos - i], visitedPos - i 1);// 当前遍历字符的位置与 visitedPos 重合elseRL[i] 1;// 中心拓展(注意处理边界)while (i - RL[i] 0 i RL[i] slen s_[i - RL[i]] s_[i RL[i]])RL[i] 1;// 更新 visitedPos 和 midPosif (i RL[i] - 1 visitedPos){visitedPos RL[i];midPos i;}// 统计回文子串数量count RL[i] / 2;}return count;
}复杂度分析
时间复杂度 O ( n ) O(n) O(n)。
空间复杂度 O ( n ) O(n) O(n)。 END
