﻿ 串的模式匹配算法之kmp - ku游体育注册页面

# 串的模式匹配算法之kmp2020-01-11

title: 串的模式匹配算法之kmp

tags: 数据结构与算法之美

author: 辰砂

1.引言

2.BF算法 BF算法设计思想：

1.举例：

public static int bfMatch(char[] s, char[] p) {int sLen = s.length;int pLen = p.length;int i = 0;int j = 0;while (i < sLen && j < pLen) {if (s[i] == p[j]) {//①如果当前字符匹配成功（即S[i] == P[j]），则i++，j++i++;j++;} else {//②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0// i - (j - 1) 表示主串的位置回到当前的下一个位置。i = i - j + 1;j = 0;}}//匹配成功，返回模式串p在文本串s中的位置，否则返回-1if (j == pLen) {return i - j;} else {return -1;}}public static void main(String[] args) {String s = "BBC ABCDAB ABCDABCDABDE";String p = "ABCDABD";System.out.println(bfMatch(s.toCharArray(),p.toCharArray()));}

2.时间复杂度说明：

1.S为B，P为A，不匹配，执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，S跟P匹配，相当于模式串要往右移动一位（i=1，j=0）

2.S跟P还是不匹配，继续执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，S跟P匹配（i=2，j=0），从而模式串不断的向右移动一位（不断的执行“令i = i - (j - 1)，j = 0”，i从2变到4，j一直为0）

3.直到S跟P匹配成功（i=4，j=0），此时按照上面的暴力匹配算法的思路，转而执行第①条指令：“如果当前字符匹配成功（即S[i] == P[j]），则i++，j++”，可得S[i]为S，P[j]为P，即接下来S跟P匹配（i=5，j=1）

4.S跟P匹配成功，继续执行第①条指令：“如果当前字符匹配成功（即S[i] == P[j]），则i++，j++”，得到S跟P匹配（i=6，j=2），如此进行下去

5.直到S为空格字符，P为字符D（i=10，j=6），因为不匹配，重新执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，相当于S跟P匹配（i=5，j=0）

6.至此，我们可以看到，如果按照暴力匹配算法的思路，尽管之前文本串和模式串已经分别匹配到了S、P，但因为S跟P不匹配，所以文本串回溯到S，模式串回溯到P，从而让S跟P匹配。

3.KMP算法（主串指针不回溯）

public static int kmpMatch(char[] s, char[] p) {int sLen = s.length;int pLen = p.length;int i = 0;int j = 0;while (i < sLen && j < pLen) {if (s[i] == p[j]) {//①如果当前字符匹配成功（即S[i] == P[j]），则i++，j++i++;j++;} else {j = next[j];}}//匹配成功，返回模式串p在文本串s中的位置，否则返回-1if (j == pLen) {return i - j;} else {return -1;}}

1.如何求next()?

1.寻找前缀后缀最长公共元素长度

j1234567891011121314151617

2.求next数组

next 数组考虑的是除当前字符外的最长相同前缀后缀，所以通过第①步骤求得各个前缀后缀的公共元素的最大长度后，只要稍作变形即可：将第①步骤中求得的值整体右移一位，然后初值赋为-1，如下表格所示：

j1234567891011121314151617

next[j]01112231123456212

3.如何求next函数值

next = 0;表明主串从下一字符si+1起和模式串重新开始匹配。i = i+1; j = 1;

设next[j] = k，则next[j+1] = ?

①若pk=pj，则有“p1…pk-1pk”=“pj-k+1…pj-1pj” ，如果在 j+1发生不匹配，说明next[j+1] = k+1 = next[j]+1。

②若pk≠pj，可把求next值问题看成是一个模式匹配问 题，整个模式串既是主串，又是子串。

4.总结

1.最开始匹配时

P跟S匹配失败

P跟S又失配，j再次等于-1，i、j继续自增，从而P跟S匹配。

P跟S失配后，P又跟S匹配。

P跟S再失配，直到P跟S匹配成功，开始执行此条指令的后半段：“如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++”。

2.P跟S匹配成功，P跟S也匹配成功, ...，直到当匹配到P处的字符D时失配（即S != P），由于P处的D对应的next 值为2，所以下一步用P处的字符C继续跟S匹配，相当于向右移动：j - next[j] = 6 - 2 =4 位。

3.向右移动4位后，P处的C再次失配，由于C对应的next值为0，所以下一步用P处的字符继续跟S匹配，相当于向右移动：j - next[j] = 2 - 0 = 2 位。

4.移动两位之后，A 跟空格不匹配，模式串后移1 位。

5.P处的D再次失配，因为P对应的next值为2，故下一步用P继续跟文本串匹配，相当于模式串向右移动 j - next[j] = 6 - 2 = 4 位。

6.匹配成功，过程结束。

void get_next(SString T, int &next[]){i= 1; next = 0; j = 0;while( i<T){if(j==0 || T[i] == T[j]){++i; ++j;next[i] = j;}elsej = next[j];}}

kMP算法的时间复杂度
{"ft_lang_label":"__label__zh","ft_lang_prob":0.831403,"math_prob":0.99843776,"size":5536,"snap":"2019-51-2020-05","text_gpt3_token_len":4350,"char_repetition_ratio":0.10737527,"word_repetition_ratio":0.30604982,"special_character_ratio":0.39884394,"punctuation_ratio":0.09327731,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9870572,"pos_list":[0,1,2],"im_url_duplicate_count":[null,1,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-01-19T19:54:55Z\",\"WARC-Record-ID\":\"<urn:uuid:5e72fbf5-c485-499a-8f4c-8078bb25e4cb>\",\"Content-Length\":\"18383\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:11e3889e-14b3-49e5-9b11-2480c3f10d6d>\",\"WARC-Concurrent-To\":\"<urn:uuid:ff18de49-1329-4bf1-b230-480d8bfc2e3f>\",\"WARC-IP-Address\":\"104.201.29.55\",\"WARC-Target-URI\":\"http://www.alittlebitoflou.com/42393/dfuws.html\",\"WARC-Payload-Digest\":\"sha1:2ZIKQP2W6AFTTUXPDV4XXYE7H3MXKIAS\",\"WARC-Block-Digest\":\"sha1:L46ZXQQKACWUJLFGA4HZQIEZBUYY3G2S\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-05/CC-MAIN-2020-05_segments_1579250594705.17_warc_CC-MAIN-20200119180644-20200119204644-00361.warc.gz\"}"}