网站实施建设流程,怎么做类似淘宝一样的网站吗,做网站用的软件,wordpress 企业沟通插件Manacher算法学习笔记 DECLARATION 引用来源#xff1a;https://www.cnblogs.com/grandyang/p/4475985.html CONTENT 用途#xff1a;寻找一个字符串的最长回文子串时间复杂度#xff1a;O(N)算法步骤#xff1a; 1.添加特殊字符 由于回文串的长度可奇可偶#xff0c;比如…Manacher算法学习笔记 DECLARATION 引用来源https://www.cnblogs.com/grandyang/p/4475985.html CONTENT 用途寻找一个字符串的最长回文子串时间复杂度O(N)算法步骤 1.添加特殊字符 由于回文串的长度可奇可偶比如bob是奇数形式的回文noon就是偶数形式的回文马拉车算法的第一步是预处理做法是在每一个字符的左右都加上一个特殊字符比如加上#那么 bob -- #b#o#b# noon -- #n#o#o#n# 这样做的好处是不论原字符串是奇数还是偶数个处理之后得到的字符串的个数都是奇数个这样就不用分情况讨论了而可以一起搞定。 2.求每个回文子串的半径 我们还需要和处理后的字符串t等长的数组p其中p[i]表示以t[i]字符为中心的回文子串的半径若p[i] 1则该回文子串就是t[i]本身。 最长子串的长度是半径减1起始位置是中间位置减去半径再除以2。 如何求p数组需要新增两个辅助变量mx和id其中id为能延伸到最右端的位置的那个回文子串的中心点位置mx是回文串能延伸到的最右端的位置这个算法的最核心的一行如下p[i] mx i ? min(p[2 * id - i], mx - i) : 1; 代码实现Leetcode #5 class Solution {
public:string longestPalindrome(string s) {// Insert #string t $#;for (int i 0; i s.size(); i) {t s[i];t #;}// Process tvectorint p(t.size(), 0);int mx 0, id 0, resLen 0, resCenter 0;for (int i 1; i t.size(); i) {p[i] mx i ? min(p[2 * id - i], mx - i) : 1;while (t[i p[i]] t[i - p[i]]) p[i];if (mx i p[i]) { //update mx idmx i p[i];id i;}if (resLen p[i]) { //update resLen resCenterresLen p[i];resCenter i;}}return s.substr((resCenter - resLen) / 2, resLen - 1);}
}; 转载于:https://www.cnblogs.com/NeilThang/p/10105874.html
