KMP字符串匹配算法-创新互联

引言

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

java代码

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元起，快前往官网查看详情吧

标题名称：KMP字符串匹配算法-创新互联
分享链接：http://bjjierui.cn/article/dpojgg.html