您的位置: 首页  >  文章  >  [kmp]kmp求字符串中子串的个数

[kmp]kmp求字符串中子串的个数

分类: 文章 • 2023-02-08 00:17:20

Oulipo
Time Limit: 1000MS   Memory Limit: 65536K
     

Description

The French author Georges Perec (1936–1982) once wrote a book, La disparition, without the letter 'e'. He was a member of the Oulipo group. A quote from the book:

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…

Perec would probably have scored high (or rather, low) in the following contest. People are asked to write a perhaps even meaningful text on some subject with as few occurrences of a given “word” as possible. Our task is to provide the jury with a program that counts these occurrences, in order to obtain a ranking of the competitors. These competitors often write very long texts with nonsense meaning; a sequence of 500,000 consecutive 'T's is not unusual. And they never use spaces.

So we want to quickly find out how often a word, i.e., a given string, occurs in a text. More formally: given the alphabet {'A', 'B', 'C', …, 'Z'} and two finite strings over that alphabet, a word W and a text T, count the number of occurrences of W in T. All the consecutive characters of W must exactly match consecutive characters of T. Occurrences may overlap.

Input

The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:

  • One line with the word W, a string over {'A', 'B', 'C', …, 'Z'}, with 1 ≤ |W| ≤ 10,000 (here |W| denotes the length of the string W).
  • One line with the text T, a string over {'A', 'B', 'C', …, 'Z'}, with |W| ≤ |T| ≤ 1,000,000.

Output

For every test case in the input file, the output should contain a single number, on a single line: the number of occurrences of the word W in the text T.

Sample Input

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

Sample Output

1
3
0

Source

BAPC 2006 Qualification

[Submit]   [Go Back]   [Status]   [Discuss]

http://poj.org/problem?id=3461

题意：题意很明确，就是用第一行的字符串来匹配第二行给出的字符串，能在第二行的字符串中找出几个第一行这样的字符串。

思路：入门KMP算法题，打出匹配串的对应部分匹配值，然后在用kmp算法来匹配。


开始学kmp算法，感觉理解算法之后代码实现还是有一定套路性的，只需要每次注意一些不同题目要求来更改些细节的代码实现即可。【目前想法】


【代码实现】

[cpp] view plain copy
 print?
  1. #include<cstdio>  
  2. #include<cstring>  
  3. using namespace std;    
  4. const int MAXW=10001,MAXT=1000001;  
  5. char W[MAXW],T[MAXT];  
  6. int next[MAXW];  
  7. int lenW,lenT;   
  8. void getnext(int lenW)  
  9. {  
  10.     int i=0,j=-1;  
  11.     next[i]=-1;  
  12.     while(i<lenW) {  
  13.         if(j==-1||W[i]==W[j]) {  
  14.             next[++i]=++j;  
  15.         }  
  16.         else j=next[j];  
  17.     }  
  18. }  
  19.   
  20. int kmp(int pos,int lenW,int lenT)  
  21. {  
  22.     int i=pos,j=0,ans=0;  
  23.     while(i<lenT) {  
  24.         if(T[i]==W[j]||j==-1) ++i,++j;  
  25.         else j=next[j];  
  26.         if(j==lenW) {  
  27.             ans++;  
  28.             j=next[j-1];  
  29.             i--;  
  30.         }  
  31.     }  
  32.     return ans;  
  33. }  
  34.   
  35.   
  36. int main()  
  37. {  
  38.     int n;  
  39.     scanf("%d",&n);  
  40.     while(n--) {  
  41.         scanf("%s%s",W,T);  
  42.         lenW=strlen(W);  
  43.         lenT=strlen(T);  
  44.         getnext(lenW);  
  45.         printf("%d\n",kmp(0,lenW,lenT));  
  46.     }  
  47.     return 0;  
  48. }  

在模式匹配算法中，KMP是比较常见的单模、高效率算法之一。在讨论KMP之前，先看看朴素的匹配算法为什么低效。普通的暴力匹配算法在每一次匹配失败之后，仅仅下移一位，并且需要重新判断整个模式串的每一个字符，见下图：

[kmp]kmp求字符串中子串的个数

第一次匹配时，首先会遍历模式串的每一个字符，但是发现模式串的第4个字符f，与文本串的第4个字符a不匹配，所以此时匹配失败；接着进行第二次匹配，文本串下移一位，即从第1个字符开始，然后同样会遍历模式串的每一个字符。这样朴素的匹配过程，假设文本串T的长度为n，模式串P的长度为m，那么可能的匹配起始点有n-m个，而每一次匹配都需要遍历整个模式串P，所以时间复杂度是幂次级别的o(m*(n-m))。显然这样复杂度的做法是比较低效的。

接下来看下KMP算法是怎么优化匹配过程的。还是分析前面的例子，当第一次匹配失败的时候，朴素算法的做法是将文本串下移一个字符，然后对于模式串则从头开始逐个字符的判断，即将文本串的第1个字符b与模式串的第0个字符a进行比较。然而其实将这一对字符进行比较是没有必要的，因为仔细观察第一次匹配过程可以知道，当第一次匹配失败的时候，文本串的0-3号字符已经确认是abba了，那么也就是说此时已经确定了模式串的第0个字符a与文本串的第1个字符b肯定是不相等的。同理，将模式串的第0个字符与文本串的第2个字符进行比较也是没有必要的。接下来，看模式串的第0个字符与文本串的第3个字符a，当然是相等的，这种情况下，就将文本串和模式串都下移一位，用同样的方式进行比较（此例的比较已完成，不用下移继续比较），以此类推，直到判断到文本串的第3个字符，也就是说将上一次匹配失败时所已经确定的文本串字符都判断完毕为止。改进后匹配过程如下图：

[kmp]kmp求字符串中子串的个数

这正是KMP算法的匹配过程，即当文本串在第4个字符失配的时候，不是按照朴素匹配算法将文本串下移一位将匹配起始位变成第1个元素b，然后再从头对模式串的每一个字符进行判断的做法，而是利用已经得到确认的文本串字符信息，直接将失配的文本串第4个字符，与模式串的第1个字符进行比较，省去中间一些没有必要进行的比较。由此可见，kmp算法将模式匹配过程的时间复杂度优化到了o(m+n)。

由上述分析可知，KMP算法进行匹配的思路就是：利用上一次失配时已经确认了的文本串字符信息，来决定下一次匹配时模式串应该用来进行比对的字符位置，而文本串用来比对的字符位置则是失配时的那个字符位置。

在上面的例子中，当文本串在第4个字符失配时，按照KMP算法的思路，应该直接将失配字符与模式串的第1个字符进行比较。经过前面的分析，已经确认了这是正确的，所以下一步的关键则是失配时模式串字符的位置应该如何计算呢？当然，不能直接将上面分析的过程翻译成算法，因为那只是一个人为的判断过程，如果要写出固定的逻辑，必须要找到相关的规律。仔细观察匹配的过程不难发现，每一次匹配所确定的文本串字符一定是模式串的某一个前缀，因为当第一次匹配开始的时候一定是从模式串的第一个字符开始判断的。再仔细观察文本串失配后，KMP算法进行的最后结果，其实就是将模式串的某一个前缀与已确定文本串字符的某一个后缀进行重合了。如下图所示：

[kmp]kmp求字符串中子串的个数

其中，灰色部分是已确认文本串字符，文本串在第i个字符a处失配，而B是已确定文本串字符的一个后缀，A则是模式串的一个后缀，如果此时是下一轮比较的正确起始位置，那么狠明显的一个条件就是A和B必须要相等，并且按照KMP跳过所有不需要比较字符的思路，还要求A和B的长度必须尽可能的大。现在问题就变成了：寻找已确定文本串字符的一个最大后缀与模式串的一个最大前缀相等。再次思考KMP算法的思路：利用上一次失配时已经确认了的文本串字符信息。因为是模式匹配，要确认文本串的字符具体是什么，一定是用模式串来判断的，而模式串肯定是已经确定了的。由上图也可以看出，已确定的文本串字符，其实就是已经判断过了的模式串字符，而它们都是模式串的一个前缀。那么问题就进一步转化为：寻找当前模式串前缀的最大公共前后缀。由于失配可能发生在模式串的任意一个字符，所以失配时的当前模式串前缀可能是模式串的任意一个前缀。所以当模式串在第i个字符失配的时候，假设当前模式串前缀的最大公共前后缀的长度为l，那么下一轮匹配模式串移动k位后将要进行比较的是第l个字符。这个l值，其实也就是KMP算法中著名的next数组值，即next[i]=l。

现在已经知道了要计算的是模式串的每一个前缀的最大公共前后缀的长度。这一步可以利用字符串前后缀的递推属性，用模式串本身来匹配本身进行计算，原理如下图所示：

[kmp]kmp求字符串中子串的个数

现在要计算next[i+1]的值。已知next[i]代表的是模式串前缀T[0-i]的最大公共前后缀长度，那么这个前缀的下一个字符位置即等于next[i]，而这个后缀的下一个字符位置就是当前的i+1，如上图中的第二个串所示。那么此时比较next[i]位置和i+i位置上的字符，这其实就是一个KMP的模式匹配的过程了，如果相等则可知当前位置的最大公共前后缀是前一个位置i的最大公共前后缀加1；如果不相等，则只能在next[i]位置之前继续寻找与i+1位置相等的字符，并且利用已经计算出来的最大公共前后缀信息跳过不不必要的比较，如下图：

[kmp]kmp求字符串中子串的个数

由此，可以写出计算next数组的算法：

[cpp] view plain copy
  1. // 模式串最大长度  
  2. const int MAX_P_LEN = 1024;  
  3. // next数组，next[i]代表模式串前缀pattern[0-i]的最大公共前后缀  
  4. // 同时，next[i]也代表当模式串在第i个位置字符失配时，下一次应该用来与当前位置的文本串字符继续比较的模式串字符位置  
  5. int next[MAX_P_LEN];  
  6.   
  7. // 构建模式串pattern的next数组值  
  8. void getFail(char pattern[])  
  9. {  
  10.     int PatLen = strlen(pattern);  
  11.     // 初始化递推边界  
  12.     next[0] = 0;  
  13.     next[1] = 0;  
  14.     // 构建模式串pattern的每一个前缀的next值，即计算其最大公共前后缀的长度  
  15.     for(int i=1; i<PatLen; ++i)  
  16.     {  
  17.         int j = next[i];  
  18.         // 在前缀中递推搜寻  
  19.         while(j && pattern[i]!=pattern[j]) j = next[j];  
  20.         next[i+1] = pattern[i]==pattern[j] ? j+1 : 0;  
  21.     }  
  22. }  

当next数组的值全部被计算出来之后，模式匹配的过程就比较简单了：分别从文本串和模式串的第一个字符开始判断，如果相等则比较下一个字符，否则失配时则按照对应位置的next值移动模式串重新进行比较，直到判断完所有的模式串字符则匹配成功，判断完所有的文本串字符则整个匹配过程结束。具体算法代码如下：

[cpp] view plain copy
  1. // 用于判断文本串text中是否包含模式串pattern  
  2. int kmp(char text[], char pattern[])  
  3. {  
  4.     int TextLen = strlen(text);  
  5.     int PatLen = strlen(pattern);  
  6.     // 当前比较的模式串字符位置  
  7.     int j = 0;  
  8.     // 比较文本串的每一个字符  
  9.     for(int i=0; i<TextLen; ++i)  
  10.     {  
  11.         // 失配时沿着失配边走，直到可以匹配或回到模式串的第一个字符  
  12.         while(j && text[i]!=pattern[j]) j = next[j];  
  13.         // 比较当前文本串字符和移动后的模式串当前字符  
  14.         if (text[i] == pattern[j]) ++j;  
  15.         // 如果模式串的所有字符都比较相等了，则完成模式匹配  
  16.         if (j == PatLen) return 1;  
  17.     }  
  18.     return 0;  
  19. }  

上面的kmp代码在第一次匹配成功后就返回了，也就是说仅仅只能判断文本串是否包含模式串。其实kmp还能找出模式串在文本串中所有出现的位置，即模式串出现的次数。具体做法也很简单，就是当每一次模式串匹配成功后，利用最后一个next数组值来移动模式串，继续进行模式匹配。匹配算法代码如下：

[cpp] view plain copy
  1. // 用于判断模式串pattern在文本串text中出现了多少次  
  2. int kmp_times(char text[], char pattern[])  
  3. {  
  4.     int times = 0;  
  5.     int TextLen = strlen(text);  
  6.     int PatLen = strlen(pattern);  
  7.     // 当前比较的模式串字符位置  
  8.     int j = 0;  
  9.     // 比较文本串的每一个字符  
  10.     for(int i=0; i<TextLen; ++i)  
  11.     {  
  12.         // 失配时沿着失配边走，直到可以匹配或回到模式串的第一个字符  
  13.         while(j && text[i]!=pattern[j]) j = next[j];  
  14.         // 比较当前文本串字符和移动后的模式串当前字符  
  15.         if (text[i] == pattern[j]) ++j;  
  16.         // 如果模式串的所有字符都比较相等了，则完成模式匹配  
  17.         if (j == PatLen)  
  18.         {  
  19.             ++times;  
  20.             // 移动模式串  
  21.             j = next[j];  
  22.         }  
  23.     }  
  24.     return times;  
  25. }  


相关推荐