大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
KMP算法的思想在于,让每一次匹配都尽可能使用先前匹配产生的信息(部分匹配表)。
成都创新互联秉承实现全网价值营销的理念,以专业定制企业官网,成都网站制作、网站设计、外贸网站建设,重庆小程序开发,网页设计制作,手机网站开发,全网营销推广帮助传统企业实现“互联网+”转型升级专业定制企业官网,公司注重人才、技术和管理,汇聚了一批优秀的互联网技术人才,对客户都以感恩的心态奉献自己的专业和所长。KMP算法的难点在于,部分匹配表的构造也在尽可能使用之前构造过程中的信息(动态规划?)。
暴力 Vs KMP暴力:失配,字串向后1位,成功匹配字符数归0。
KMP:失配,字串向后n位,成功匹配数m位。n,m的计算即KMP算法的核心。
找规律?? ??
abcdabcy abcdabcy
a? a?
abcdabcy abcdabcy
ab? ab?
abcdabcy abcdabcy
abc? abc?
abcdabcy abcdabcy
abcd? abcd?
abcdabcy abcdabcy
abcda abcda?
abcdabcy abcdabcy
abcdab? abcdab?
abcdabcy abcdabcy
abcdabc? abcdabc?
abcdabcy abcdabcy
abcdabcy
abcdabcy
观察得知,移动的位数分别需要考察 a ab abc abcd abcda abcdab abcdabc的前缀和后缀是否一样。same[index]
可以理解为pattern[index]
之前的前后缀匹配大长度
为了使得move[index] = index - same[index]
,规定same[0] = -1
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
pattern[index] | a | b | c | d | a | b | c | y |
same[index] | -1 | 0 | 0 | 0 | 0 | 1 | 2 | 3 |
move[index] | 1 | 1 | 2 | 3 | 4 | 4 | 4 | 4 |
上一部分中最后的表格能极大的帮助我们完成字符串的匹配,它也就是所谓的部分匹配表。使用该表的时机即pattern[index]
无法匹配,所以该表也称失配函数
以 aabaabaaa为例子,构造部分匹配表
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
pattern[index] | a | a | b | a | a | b | a | a | a |
same[index] | -1 | 0 | 1 | 0 | 1 | 2 | 3 | 4 | 5 |
move[index] | 1 | 1 | 1 | 3 | 3 | 3 | 3 | 3 | 3 |
类似动态规划问题,如果我们已知same[index-1] = k
,那么pattern[0...(index-2)]
的前后缀匹配大长度已知,即pattern[0...k-1] == pattern[(index-k-1)...(index-2)]
。
在求same[index]
时我们需要考虑新的字符pattern[index - 1]
,也就增加了1个后缀需要考虑的字符。
pattern[k] == pattern[index-1]
,那么pattern[0...k] == pattern[(index-k-1)...(index-1)]
,那么same[index] = same[index - 1] + 1
pattern[k] != pattern[index-1]
,则需要回溯到更小的匹配长度,一定小于k。我们考虑same[k]
的定义,即pattern[k]
之前的前后缀大匹配长度,是能回溯到的最好的匹配长度。pattern[same[k]]
和pattern[index - 1]
的大小关系,无法得出结果则继续回溯。same[0] == -1
,则same[index] = 0
public static int[] getSame(String modelString) {int[] same = new int[100];
same[0] = -1;
int i = 0;
int j = same[i];
while (i< modelString.length()) {if (j == -1 || modelString.charAt(i) == modelString.charAt(j)) {// same[i+1] = same[i] + 1
i++;
j++;
same[i] = j;
} else {// backtrack
j = same[j];
}
}
return same;
}
最后same
可能就是其他文章中提到的next
数组
KMP字符串匹配算法【双语字幕】
wiki百科
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧