Manacher

问题

寻找字符串中的最长回文串

传统做法

字符串首字符前加一个特殊字符 ‘#’ 末尾字符加一个特殊字符 ‘#’ 相邻字符间也加上特殊字符 ‘#’
遍历字符串，除特殊字符外，以每个字符作为回文字符串的中心向外扩张

思考

很明显这种做法的时间复杂度是很高的，所以采用manacher进行提速

提速

数据

记录数据R表示目前最长回文串的的半径

记录数据M表示目前最长回文串的中心

数组parr存储每个字符为中心的最长回文串的半径

思路

根据遍历字符下标i和R的关系分为以下情况

i在R范围外，则自己往外扩
i在R范围内，根据以M做对称点的i'情况分为三种情况

parr[i']在R范围内，但不与R边缘位置重叠，则parr[i] = parr[i']
parr[i']超出R范围，则parr[i] = R - i
parr[i']在R范围内，与R边缘位置重叠，也是自行扩，有一段距离不用判断: R - i

实现

string f1(string str)
{string res;for(int i = 0;i < str.size() * 2 + 1;i++){res += i & 1 ? str[i / 2] : '#';}return res;
}

int f2(string str)
{if(str.size() == 0) return 0;int R = -1;int M = -1;string pstr = f1(str);int* parr = new int(pstr.size());int Rmax = INT32_MIN;for(int i = 0;i < pstr.size();i++){/******不用判断的半径******/int parr[i] = R > i ? min(parr[2 * M - i],R - i) : 1;while(i + parr[i] < pstr.size() && i - parr[i] > -1){if(str[i + parr[i]] == str[i - parr[i]]){parr[i]++;}else break;}if(parr[i] + i > R){R = i + parr[i];M = i;}Rmax = max(Rmax,parr[i]);}delede[] parr;return Rmax - 1;
}