马拉车算法 解决回文串问题【算法分析】

今天爱分享给大家带来马拉车算法 解决回文串问题【算法分析】,希望能够帮助到大家。

对于回文串,简单说即正着念和反着念是一样的字符串,如abba。用常规的暴力方法,即以一个字符为中心,两边分别外扩,比较每个字符。这种方法需要分奇偶来讨论,即如aba和abba这两种情况。
1.马拉车算法首先需要对字符串进行处理,在字符串开头结尾及字符间穿插同一个特殊字符,该字符可以是任何字符,不影响结果。

马拉车算法 解决回文串问题【算法分析】插图

处理后的字符串,不管原字符串长度是奇是偶,都变成了奇,这样就可以以同一种方式处理了。
2.这里引入两个变量,分别是R和C。下面将解释两个变量的意义。
假设下图方框表示以a为中心的回文字符串

马拉车算法 解决回文串问题【算法分析】插图(1)

我们用一个数组array来表示对以应位置的字符为中心,其最长的回文字符串长度。即array[7] = 8。那么我们知道,在以a为中心的回文字符串中,因为对称的关系,左右两边有着相同的子串

马拉车算法 解决回文串问题【算法分析】插图(2)

依照这个特性,后面字符的array值,是可以参考前面对称位置字符的array值的。R的作用是框定当前回文半径最长的距离(只增不减),即上图14的位置,而c则是以R为半径的回文串中心。这里分两种情况。
(1)若当前i的位置小于R(即如上图在红框内),则以其对称位置2c-i的array值为基础,再向外扩展。
(2)若i大于R,即在红框外,array初始值设为1,则需要按照之前的方式,两边展开来比较,无优化。比较完后再更新R和C值。

//预先处理字符串
string getmancher(string str)
{
    string res(2*str.length()+1,0);
    int j = 0;
    for(size_t i = 0;i=R?1:min(array[2*C-i],R-i-1);
            while(i+array[i]>=0 && i+array[i]

                    

人已赞赏
Java

LongAdder和AtomicLong哪个性能更好【图文分析原因】

2020-10-29 15:50:11

Java

缓存穿透 如何设计解决方法【大神分析】

2020-10-29 15:56:44

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧