- //求字符串s中最大回文的长度,要求字符串s不包含字符‘#’
- int manacher(const string &s)
- {
- if (s.size() <= 1)
- return s.size();
- //往s每个字符之间以及s的首尾都插入‘#’
- string str(s.size() * 2 + 1, '#');
- for (int i = 0, j = 1; i<s.size(); ++i, j += 2)
- str[j] = s[i];
- int maxr = 2, id = 1, size = str.size();//maxr是当前最大回文的半径
- vector<int> p(size, 1);
- p[1] = 2;
- for (int i = 2; i <= size-3; ++i)
- {
- int maxright = p[id] + id - 1;
- if (i>maxright)
- {
- while (i - p[i] >= 0 && i + p[i]<size && str[i + p[i]] == str[i - p[i]])
- ++p[i];
- }
- else
- {
- int idleft = id - p[id] + 1;
- int k = i - id, j = id - k, tmp = j - p[j] + 1;//i和j关于id对称
- if (tmp>idleft)
- p[i] = p[j];
- else if (tmp<idleft)
- p[i] = p[id] - k;
- else
- {
- p[i] = p[j];
- while (i - p[i] >= 0 && i + p[i]<size && str[i + p[i]] == str[i - p[i]])
- ++p[i];
- }
- }
- if (p[i] + i>p[id] + id)
- id = i;
- maxr = max(maxr, p[i]);
- }
- return maxr - 1;
- }
来源: http://www.phpxs.com/code/1004188/