Manacher
解决最长回文子串问题
引入两个辅助变量 id, mx
先预处理插入#
,再分两种情况:
- 回文串
p[2*id-i] (记 p[j])
包含在大子串内部,p[i]
直接等于p[j]
-
p[j]
部分包含在大子串内,这一部分p[i]
等于p[j]
,后续接着扩展
//输入,并处理得到字符串s
int p[1000], mx = 0, id = 0;
memset(p, 0, sizeof(p));
for (i = 1; s[i] != '\0'; i++)
{
p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
while (s[i + p[i]] == s[i - p[i]])
p[i]++;
if (i + p[i] > mx)
{
mx = i + p[i];
id = i;
}
}
//找出p[i]中最大的
Maximum Gap
找出排序后相邻元素的最大差值,要求 O(n)
如 [9, 3, 1, 10] 返回 6
利用桶排序的思想,且每个桶会记录存放的最大值和最小值。
不妨用 N-1 个桶放置,这样每个桶的间距gap
为(max-min)/(N-1)
(注:桶的数量和间距有待进一步考证)
然后扫一遍把每个数num
放入第(num-min)/gap
个桶中(实际上应该再加一个桶)
最后找到间隔连续空桶最多的两个桶即可
网友评论