做搜狐网站页面,广州网络公司人气排名,wordpress文章添加忽略,搜索网站排名优化策略看了好久的Manacher算法#xff0c;觉得还是要自己画一遍#xff0c;自己把代码写一遍才能理解
下面分享一下#xff0c;如果有错#xff0c;希望指正
简陋版本的#xff0c;但是他基本只是做到了求取最长回文字符串#xff0c;严格来说它并不是Manacher’s Algorithm-…看了好久的Manacher算法觉得还是要自己画一遍自己把代码写一遍才能理解
下面分享一下如果有错希望指正
简陋版本的但是他基本只是做到了求取最长回文字符串严格来说它并不是Manacher’s Algorithm-马拉车算法
#includestdio.h 、char qdu[100050];
int manachar()
{int i;int res 0;for (i 1; qdu[i]; i){int l i;int r i;while (qdu[i] qdu[r 1])r;i r;while (qdu[l - 1] qdu[r 1]) {r;l--;}if (res r - l 1)res r - l 1;}return res;
}
int main()
{int loop;qdu[0] $;gets(qdu 1);printf(%d\n, manachar());return 0;
}Manacher’s Algorithm-马拉车算法 时间复杂度O(n)
互联网侦察微信公众号讲解虽然文章很长但是他讲解的十分清楚
这篇博文简单的介绍了思路
下面是核心代码我们先看图
//Manacher算法计算过程
int MANACHER(char *st, int len)
{int mx 0, ans 0, po 0;//mx即为当前计算回文串最右边字符的最大值for (int i 1; i len; i){if (mx i)Len[i] min(mx - i, Len[2 * po - i]);//在Len[j]和mx-i中取个小elseLen[i] 1;//如果imx要从头开始匹配while (st[i - Len[i]] st[i Len[i]])Len[i];if (Len[i] i mx)//若新计算的回文串右端点位置大于mx要更新po和mx的值{mx Len[i] i;po i;}ans max(ans, Len[i]);}return ans - 1;//返回Len[i]中的最大值-1即为原串的最长回文子串额长度
}首先对字符串进行预处理处理原因是防止偶数问题可看前面的博文 处理后的结果进行Manacher算法。 第一个是0其余默认从1开始计数 首先看3 的左右都是#号所以11 2 到了1它可以数到6碰到了就不相等了而他的回文字符串长度也是6 等到了1右边的#号我们就可以根据对称特点求出他和1左边的#号是同一个值前提是这个没有超过有边界黄色横线所示 到这里基本就结束了 这里给出完整代码可以自己跑一编看看效果
#define maxn 1000010
#include cstdio
#include iostream
#include algorithmusing namespace std;char str[maxn] {3212343219};//原字符串
char tmp[maxn 1];//转换后的字符串
int Len[maxn 1];//转换原始串
int INIT(char *st)
{int i, len strlen(st);tmp[0] ;//字符串开头增加一个特殊字符防止越界for (i 1; i 2 * len; i 2){tmp[i] #;tmp[i 1] st[i / 2];}tmp[2 * len 1] #;tmp[2 * len 2] $;//字符串结尾加一个字符防止越界tmp[2 * len 3] 0;return 2 * len 1;//返回转换字符串的长度
}
//Manacher算法计算过程
int MANACHER(char *st, int len)
{int mx 0, ans 0, po 0;//mx即为当前计算回文串最右边字符的最大值for (int i 1; i len; i){if (mx i)Len[i] min(mx - i, Len[2 * po - i]);//在Len[j]和mx-i中取个小elseLen[i] 1;//如果imx要从头开始匹配while (st[i - Len[i]] st[i Len[i]])Len[i];if (Len[i] i mx)//若新计算的回文串右端点位置大于mx要更新po和mx的值{mx Len[i] i;po i;}ans max(ans, Len[i]);}return ans - 1;//返回Len[i]中的最大值-1即为原串的最长回文子串额长度
}int main()
{int len INIT(str);MANACHER(tmp, len);
}
