字符串模式匹配- KMP 主讲：朱佳 博士 华南师范大学计算机学院.

Presentation on theme: "字符串模式匹配- KMP 主讲：朱佳 博士 华南师范大学计算机学院."— Presentation transcript:

1 字符串模式匹配- KMP 主讲：朱佳 博士 华南师范大学计算机学院

2 KMP算法 提纲 一.由朴素匹配到KMP 二. KMP背景介绍 三.KMP核心——跳转表next[] 四. next[]的计算

3 问题描述 给两个字符串S,T，如S=“aaaaaaaaaaaaaaaaaaab”, T= “aaaaaaaab”，现在要求T是否是S的字串。

4 朴素匹配算法 一般匹配字符串时，我们从目标字符串str（假设长度为n）的第一个下标选取和ptr长度（长度为m）一样的子字符串进行比较，如果一样，就返回开始处的下标值，不一样，选取str下一个下标，同样选取长度为n的字符串进行比较，直到str的末尾（实际比较时，下标移动到n-m）。这样的时间复杂度是O(n*m)。

5 朴素匹配算法 int Index_BF ( char S [ ], char T [ ], int pos ) {
/* 若串 S 中从第pos(S 的下标0≤pos<StrLength(S))个字符 起存在和串 T 相同的子串，则称匹配成功，返回第一个 这样的子串在串 S 中的下标，否则返回 -1    */ int i = pos, j = 0; while ( S[i+j] != '\0'&& T[j] != '\0') if ( S[i+j] == T[j] ) j ++; // 继续比较后一字符 else i ++; j = 0; // 重新开始新的一轮匹配 } if ( T[j] == '\0') return i; // 匹配成功   返回下标 return -1; // 串S中(第pos个字符起)不存在和串T相同的子串

6 O(nm)的解法 那么还有没有更快的方法呢？ 首先很容易想到的就是O(nm)的解法，S串的长度为n，
T串的长度为m。直接两重循环枚举，看是否会匹配。 那么还有没有更快的方法呢？

7 KMP算法 二.KMP背景介绍 在文本编辑中，我们经常要在一段文本中某个特定的位置找出某个特定的字符或模式。再比如，在HTTP协议里的字节流,有各种关键的字节流字段,对HTTP数据进行解释就需要用到模式匹配算法。由此，便产生了字符串的匹配问题。 KMP算法是由Knuth，Morris，Pratt三人共同提出的模式匹配算法，其对于任何模式和目标序列，都可以在线性时间内完成匹配查找，而不会发生退化，是一个非常优秀的模式匹配算法。 为何简化了时间复杂度：  充分利用了目标字符串ptr的性质（比如里面部分字符串的重复性，即使不存在重复字段，在比较时，实现最大的移动量），Knuth–Morris–Pratt algorithm， 大神knuth KMP算法：可以实现复杂度为O(m+n) 为何简化了时间复杂度：  充分利用了目标字符串ptr的性质（比如里面部分字符串的重复性，即使不存在重复字段，在比较时，实现最大的移动量）。  上面理不理解无所谓，我说的其实也没有深刻剖析里面的内部原因。

8 KMP算法 二.由朴素匹配到KMP 假设有目标字符串(Target)T=b a b c b a b c a b c a a b c a b c a b c a c a b c，我们要在其中找到模式字符串（Pattern）P=a b c a b c a c a b。 如何做更为高效呢？ 朴素匹配的时间复杂度为O(m*n)； KMP的时间复杂度为O(m+n)。 由朴素匹配，我们要做16次，而KMP算法仅匹配了6次就找到了模式字符串 实际效果，后面可以会仔细讲。 Kmp6次，普通的16次

9 三.KMP算法核心——跳转表next[] KMP算法 其实，模式串往往含有一定的信息——前缀包含。
对于模式串而言，其前缀字符串，有可能也是模式串中的非前缀子串，这个问题我称之为前缀包含问题。 以模式串a b c a b c a c a b为例，其前缀的4个字符a b c a，正好也是模式串的一个子串a b c (a b c a) c a b，所以当目标串与模式串执行匹配的过程中，如果直到第 8 个字符才匹配失败，同时也意味着目标串当前字符之前的 4 个字符，与模式串的前 4 个字符是相同的，所以当模式串向后移动的时候，可以直接将模式串的第 5 个字符与当前字符对齐，执行比较，这样就实现了模式串一次性向前跳跃多个字符。 所以当模式串向后移动的时候，可以直接将模式串的第 5 个字符与当前字符对齐，不需要像朴素那样一个个排序对齐， 那么每次要跳跃多少呢？这与跳转表next[]存储的数值相关。

10 三.KMP算法核心——跳转表next[] KMP算法 模式字符串P= a b c a b c a c a b，其跳转表为：
观察，是否看的明白？如何计算next[j], 后面再详细说, 其实这里跳转表是计算错误的，只是为了下图讲解方便，先不要在意， 假设已有数组 void  getNext(const char P[],int next[]){     int  m=strlen(P);     int i=0,j;     j=next[0]=-1;     while(i<m){       while(-1!=j && P[i]!=P[j])j=next[j];       next[++i]=++j;     }   }

11 三.KMP算法核心——跳转表next[] 所以关键是next[] 的计算，也就是所谓的部分匹配值 KMP算法
此时 pattern 串的第 1 个字母与 target[6]对齐，从 6 向后依次匹配目标串，到 target[13]时发现 target[13]='a'，而 pattern[8]='c'，匹配失败，此时 next[8]=5，所以将模式串向后移动 8-next[8] = 3 个字符，将pattern[5]与 target[13]对齐，然后由 target[13]依次向后 执行匹 要仔细搞懂这里，黑板演算，移动位数 = 已匹配的字符数 - 对应的部分匹配值 = j-next[j],所以8-5 = 3， ，next 是对应的部分匹配之 2） 5-next[5]=5-1=4,所以向后移动4位 3)变成pattern[1]与target[13]对齐,这时又是第8位与target[20]不匹配，因此往前挪3位，将pattern[5]与 target[20]对齐。 所以关键是next[] 的计算，也就是所谓的部分匹配值 配操作。在整个匹配过程中，无论模式串如何向后滑动，目标串的输入字符都不会回溯，直到找到模式串，或者遍历整个目标串都没有发现匹配模式为止。 所以关键是next[] 的计算，也就是所谓的部分匹配值

12 "部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度
KMP算法 四. next[]的计算——部分匹配值 "部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。

13 四. next[]的计算——部分匹配值 KMP算法
"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，所以，要实现KMP算法，必须要计算出p串各个子串的部分匹配长度。通常KMP算法教材所说的next数组（或者其他名字）本质上指的就是这个“部分匹配值”，因为知道next数组的意义，所以最笨的方法就是枚举+检验找出部分匹配值，当然这样做显得太low了。 其实你可以把这个问题单独考虑成一个动态规划问题——“求一个字符串s的最大前缀后缀匹配长度”。

14 ababaca 四. next[]的计算——部分匹配值练习 KMP算法
*注意最长前缀：是说以第一个字符开始，但是不包含最后一个字符。 写出next 表 比如aaaa相同的最长前缀和最长后缀是aaa。**  对于目标字符串ptr，ababaca，长度是7，所以next[0]，next[1]，next[2]，next[3]，next[4]，next[5]，next[6]分别计算的是  a，ab，aba，abab，ababa，ababac，ababaca的相同的最长前缀和最长后缀的长度。由于a，ab，aba，abab，ababa，ababac，ababaca的相同的最长前缀和最长后缀是“”，“”，“a”，“ab”，“aba”，“”，“a”,所以next数组的值是[-1,-1,0,1,2,-1,0]，这里-1表示不存在，0表示存在长度为1，2表示存在长度为3。这是为了和代码相对应

15 四. next[]的计算——举例说明 KMP算法
“部分匹配值”就是“前缀”和“后缀”的最长的共有元素的长度。以“ABCDABD”为例，所以，要实现KMP算法，必须要计算出p串各个子串的部分匹配长度。通常KMP算法教材所说的next数组（或者其他名字）本质上指的就是这个“部分匹配值”，next[i]表示从0到i的子串的部分匹配值。有时候将next[0]设为-1，那是为了简化编程实现，他们没有本质区别，看这个实际例子，s是目标，p匹配(pattern) 第一个图，绿色为匹配好的，知道黄色字符发现不匹配红色字符。第二个图右移一定距离后看是否能匹配红色字符。如果刚好匹配，那么就继续下一个字符匹配，没什么好说的。

16 四. next[]的计算——举例说明 再次尝试匹配红色字符 部分匹配值 KMP算法
在例子里体现部分匹配值，知道了部分匹配多少，就知道右移多少， 如何算？ 部分匹配就是next[i],你可以像我们之前那样全部枚举，但效率不高 部分匹配值

17 四. next[]的计算——举例说明 右移长度 KMP算法
理解为求一个字符串s的最大前缀后缀匹配长度，先假设我们已经求出next[0]到next[i]的值，而（关键）现在要求next[i+1]。如下图所示，绿色的部分是next[i]表示的部分匹配长度，也就是从0到i的子串的部分匹配长度。红色小块代表第i+1个元素。假设我们用两个p为例子来求，实际想知道next[i+1]和next[i]的关系

18 四. next[]的计算——举例说明 ？？？ KMP算法 失配说明要继续右移，理解为求一个字符串s的最大前缀后缀匹配长度，
先假设我们已经求出next[0]到next[i]的值，而现在要求next[i+1]。如下图所示，绿色的部分是next[i]表示的部分匹配长度，也就是从0到i的子串的部分匹配长度。红色小块代表第i+1个元素。 ？？？

19 四. next[]的计算——举例说明 KMP算法
失配情况下，于是我们将p右移一段距离，为了区分，这里把下面的p称作p‘，他们其实是一样的。部分匹配长度next[i] = 右移长度 + 部分匹配长度x，黑板 “部分匹配长度x” = 上图中蓝色部分的部分匹配长度 = next[j]。 注意，next[j]是已知的（因为j一定小于i，而且我们假设next[0]到next[i]事先已经求出来了），所以回想刚才的公式 next[i] = 右移长度 + next[j]，我们可以计算出“右移长度了”！ J是多少，其实**** j = next[i]****。回想next数组的定义，next[i]表示子串p[0..i]的部分匹配长度，而j刚好就是子串p[0..i]的部分匹配长度。 J是部分匹配长度， next(j)是部分匹配长度的部分匹配长度

20 四. next[]的计算——举例说明 KMP算法 J=next[i]

21 四. next[]的计算——代码 处理匹配 处理失配 KMP算法

22 四. next[]的计算——代码 KMP算法 是不是和求next数组的代码很像，大致总结一下求next数组的特点：

23 KMP 时间上的优势 KMP算法可以做到匹配过程接近O(n)的复杂度，预 处理过程接近O(m)的复杂度。比之前提到的暴力匹 配做了很大的优化。 O(m+n)

24 最简单的KMP题，找出第一个字符串在第二个字符串中出现次数，Oulipo为Ouvroir de littérature potentielle缩写,音译“乌力波”,直译“潜在文学工场”,是一个由作家和数学家等组成的打破文本界限的松散的国际写作团体

25 描述法国作家乔治·佩雷克（Georges Perec，1936-1982）曾写过一本名为“La disparition”的书，没有字母“e”。他是Oulipo集团的成员。
这本书的引用：Tout avait Pair normal, mais tout s’affirmait faux. Tout avait Fair normal, d’abord, puis surgissait l’inhumain, l’affolant. Il aurait voulu savoir où s’articulait l’association qui l’unissait au roman : stir son tapis, assaillant à tout instant son imagination, l’intuition d’un tabou, la vision d’un mal obscur, d’un quoi vacant, d’un non-dit : la vision, l’avision d’un oubli commandant tout, où s’abolissait la raison : tout avait l’air normal mais… 佩雷克可能会在接下来的比赛中获得高分（或者更低）。人们被要求在一些主题上写一个甚至是有意义的文本，尽可能少地出现一个给定的“单词”。我们的任务是为陪审团提供一个计算这些事件的程序，以获得竞争对手的排名。这些竞争对手经常写出非常长的文本，带有无意义的含义;一系列500,000连续‘T’并不罕见。他们从不使用空格。 因此，我们希望快速找出文本中出现单词（即给定字符串）的频率。更正式地：给出字母{A‘，’B‘，’C‘，...，’Z‘}和该字母表上的两个有限字符串，单词W和文本T，计算T中W的出现次数，W的所有连续字符必须与T的连续字符完全匹配。事件可能重叠。 最简单的KMP题，找出第一个字符串在第二个字符串中出现次数

26 最简单的KMP题，找出第一个字符串在第二个字符串中出现次数，三个测试样例

27 #include <stdio.h> #include <string.h> int next[10005];
     int next[10005];    char str1[ ],str2[10005];     int cnt;     void get_next(int len2)//生成next数组      {         int i = 0,j = -1;         next[0] = -1;         while (i<len2)         {             if(j == -1 || str2[i] == str2[j])             {                 i++;                 j++;        next[i] = j;        }             else                 j = next[j];         }     }     最简单的KMP题，找出第一个字符串在第二个字符串中出现次数

28 int kmp(int len1,int len2)//kmp算法， 根据next 移位 { int i=0,j=0;
{         int i=0,j=0;          get_next(len2);      while(i<len1)          {              if(j==-1||str1[i]==str2[j])          {               ++i;     ++j;     }             else                  j=next[j];     if(j == len2)             {                  cnt++;                 j = next[j];             }         }     }    int main()     {         int n;          int len1,len2;       scanf("%d",&n);       getchar();         while(n--)         {             gets(str2);           gets(str1);             len1 = strlen(str1);             len2 = strlen(str2);           cnt = 0;             kmp(len1,len2);           printf("%d\n",cnt);         }         return 0;     }  最简单的KMP题，找出第一个字符串在第二个字符串中出现次数， 但是这代码里str2是匹配字符串，str1 是目标字符串。

29 思路：KMP，next表示模式串如果第i位(设str[0]为第0位)与文本串第j位不匹配则要回到第next[i]位继续与文本串第j位匹配。则模式串第1位到next[n]与模式串第n-next[n]位到n位是匹配的。所以思路和上面一样，如果n%（n-next[n]）==0,则存在重复连续子串，长度为n-next[n]。 例如：a    b    a    b    a    b next:-1   0    0    1    2    3    4 next[n]==4,代表着，前缀abab与后缀abab相等的最长长度，这说明，ab这两个字母为一个循环节，长度=n-next[n];

30 if(len%(len-next[len])==0)
int main(){     while(~scanf("%s",s)){       if(s[0]=='.')break;       Memset(next,0);       getNext(s,next);       int  len=strlen(s);       if(len%(len-next[len])==0) printf(“%d\n”,len/(len-next[len])); //因为要满足s=a^n       else printf("1\n");     }     return 0;   }  #include <iostream>   #include <cstdio>   #include <cstring>   #define Memset(x, a) memset(x, a, sizeof(x))   using  namespace std;   const int N=1e6+10;   int next[N];   char  s[N];      void  getNext(const char P[],int next[]){     int  m=strlen(P);     int i=0,j;     j=next[0]=-1;     while(i<m){       while(-1!=j && P[i]!=P[j]) j=next[j];       next[++i]=++j;     }   }   思路：KMP，next表示模式串如果第i位(设str[0]为第0位)与文本串第j位不匹配则要回到第next[i]位继续与文本串第j位匹配。意思直到模式串第1位到next[n]与模式串第n-next[n]位到n位是匹配的。所以思路和上面一样，如果n%（n-next[n]）==0,则存在重复连续子串，长度为n-next[n]。 例如：a    b    a    b    a    b next:-1   0    0    1    2    3    4 next[n]==4,代表着，前缀abab与后缀abab相等的最长长度，这说明，ab这两个字母为一个循环节，长度=n-next[n];