KMP:
字符串匹配，朴素的匹配是直接暴力，暴力会产生多余的匹配，没有利用到匹配串自身的特点，KMP优化，先求出匹配串自身的最长覆盖字串，每次匹配失败时，直接跳到下一个可能匹配的位置。避免多余的匹配。关键点：计算匹配串每个字符匹配失败时，跳到的位置。
eg:
asdeabcabcdefa a 和 t 匹配失败 跳到下一个可能产生匹配的位置 asdeabcabcdefasdfg
abcte -----------------------------------------------> abcte
Manacher:
字符串回文计算，朴素的方式是直接暴力，枚举每个点，然后向两边扩展, Manacher思想，利用回文本身的特点，跳过多余的字符比较。
朴素和Manacher方式，都先预处理一下字符串，eg: "asdfx" -> "$#a#s#d#f#x#" 消除字符串长度分奇偶的麻烦
朴素方式_O(n^2): s字符串数组，l记录每个位置，以该位置为中心的回文半径
for i = 1 -> n
l[i] = 1;
while( s[i - l[i]] == s[i + l[i]] )l[i]++;
Manacher_O(n): 记录向右扩展的最右端位置，和索引
for i = 1 -> n
if( maxRight > i )
{
// Manacher优化关键：(ind<<1) - i 为 i 位置 关于 ind 位置 的 对称位置
// maxRight - i 为 i位置 到 记录的最右端的距离
// 可以想到 l[i] 最小为 以上两者的最小值，这就跳过了 多余的 比较
l[i] = l[(ind<<1) - i] < (maxRight - i) ? l[(ind<<1) - i] : (maxRight - i);
}
else
{
l[i] = 1;
}
while( s[i - l[i]] == s[i + l[i]] )l[i]++;
if( i + l[i] > maxRight )
{
maxRight = i + l[i];
ind = i;
}
posted on 2012-01-27 12:41
Lshain 阅读(567)
评论(0) 编辑 收藏 引用 所属分类:
字符串 算法 记录