KMP算法,oj2087,Oulipo

超、凢脫俗 2022-04-15 02:46 161阅读 0赞

对于一些简单的查找我们可以用c库函数strstr

#include <stdio.h>
 #include <string.h>
 
 typedef char* Position;
 #define NotFound NULL
 
 int main()
 {
 	char string[] = "This is a simple example.";
 	char pattern[] = "simple";
 	Position p = strstr( string, pattern );
 	if ( p == NotFound ) printf("Not Found.\n");
 	else printf("%s\n", p);
 	return 0;
 }

但是时间复杂度太高

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKQ0hFTjEyMjE_size_16_color_FFFFFF_t_70][]

因此我们需要去学习KMP算法，时间复杂度为O (n + m )

用kmp算法最重要的就是求next值

具体求法我传到了资源库，有时间的话会过来完善下

<table> 
 <tbody> 
 <tr> 
 <td style="border-color:#000000;vertical-align:top;width:57px;"> pattern </td> 
 <td style="border-color:#000000;vertical-align:top;width:57px;"> A </td> 
 <td style="border-color:#000000;vertical-align:top;width:58px;"> B </td> 
 <td style="border-color:#000000;vertical-align:top;width:57px;"> C </td> 
 <td style="border-color:#000000;vertical-align:top;width:57px;"> A </td> 
 <td style="border-color:#000000;vertical-align:top;width:57px;"> B </td> 
 <td style="border-color:#000000;vertical-align:top;width:58px;"> C </td> 
 <td style="border-color:#000000;vertical-align:top;width:57px;"> A </td> 
 <td style="border-color:#000000;vertical-align:top;width:57px;"> C </td> 
 <td style="border-color:#000000;vertical-align:top;width:57px;"> A </td> 
 <td style="border-color:#000000;vertical-align:top;width:57px;"> B </td> 
 </tr> 
 <tr> 
 <td style="background-color:#ebebeb;border-color:#000000;vertical-align:top;width:57px;"> J </td> 
 <td style="background-color:#ebebeb;border-color:#000000;vertical-align:top;width:57px;"> 0 </td> 
 <td style="background-color:#ebebeb;border-color:#000000;vertical-align:top;width:58px;"> 1 </td> 
 <td style="background-color:#ebebeb;border-color:#000000;vertical-align:top;width:57px;"> 2 </td> 
 <td style="background-color:#ebebeb;border-color:#000000;vertical-align:top;width:57px;"> 3 </td> 
 <td style="background-color:#ebebeb;border-color:#000000;vertical-align:top;width:57px;"> 4 </td> 
 <td style="background-color:#ebebeb;border-color:#000000;vertical-align:top;width:58px;"> 5 </td> 
 <td style="background-color:#ebebeb;border-color:#000000;vertical-align:top;width:57px;"> 6 </td> 
 <td style="background-color:#ebebeb;border-color:#000000;vertical-align:top;width:57px;"> 7 </td> 
 <td style="background-color:#ebebeb;border-color:#000000;vertical-align:top;width:57px;"> 8 </td> 
 <td style="background-color:#ebebeb;border-color:#000000;vertical-align:top;width:57px;"> 9 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000;vertical-align:top;width:57px;"> next </td> 
 <td style="border-color:#000000;vertical-align:top;width:57px;"> -1 </td> 
 <td style="border-color:#000000;vertical-align:top;width:58px;"> -1 </td> 
 <td style="border-color:#000000;vertical-align:top;width:57px;"> -1 </td> 
 <td style="border-color:#000000;vertical-align:top;width:57px;"> 0 </td> 
 <td style="border-color:#000000;vertical-align:top;width:57px;"> 1 </td> 
 <td style="border-color:#000000;vertical-align:top;width:58px;"> 2 </td> 
 <td style="border-color:#000000;vertical-align:top;width:57px;"> 3 </td> 
 <td style="border-color:#000000;vertical-align:top;width:57px;"> -1 </td> 
 <td style="border-color:#000000;vertical-align:top;width:57px;"> 0 </td> 
 <td style="border-color:#000000;vertical-align:top;width:57px;"> 1 </td> 
 </tr> 
 </tbody> 
</table>

下面是具体的代码实现

#include <stdio.h>
 #include <string.h> 
 #include <stdlib.h>
 //match 相当于next
 typedef int Position;
 #define NotFound -1
 
 void BuildMatch( char *pattern, int *match )
 {
 Position i, j;
 int m = strlen(pattern);
 match[0] = -1;
 
 for ( j=1; j<m; j++ ) {
 i = match[j-1];
 while ( (i>=0) && (pattern[i+1]!=pattern[j]) )//不匹配时，回退
 i = match[i];
 if ( pattern[i+1]==pattern[j] ) // 后面的匹配上了
 match[j] = i+1;
 else match[j] = -1;
 }
 }
 
 Position KMP( char *string, char *pattern )
 {
 int n = strlen(string); // O(n)
 int m = strlen(pattern); // O(m)
 Position s, p, *match;
 
 if ( n < m ) return NotFound;
 match = (Position *)malloc(sizeof(Position) * m);
 BuildMatch(pattern, match);
 s = p = 0;
 while ( s<n && p<m ) { //O(n)
 if ( string[s]==pattern[p] ) { //匹配到了
 s++; p++;
 }
 else if (p>0) p = match[p-1]+1; //前面匹配不到的时候，回溯到[p-1]+1
 else s++; //一开始就不匹配
 }
 return ( p==m )? (s-m) : NotFound;
 }
 
 int main()
 {
 char string[] = "This is a simple example.";
 char pattern[] = "simple";
 Position p = KMP(string, pattern);
 if (p==NotFound) printf("Not Found.\n");
 else printf("%s\n", string+p);
 return 0; 
 }

下面是一些OJ题的应用

2087剪花布条

Problem Description

一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？

Input

输入中含有一些数据，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见\#字符，则不再进行工作。

Output

输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就老老实实输出0，每个结果之间应换行。

Sample Input

abcde a3

aaaaaa aa

Sample Output

0 3

#include <stdio.h>
 
 const int maxn = 10005;
 int next[maxn];
 
 void get_next( char * s );
 int kmp( char *string, char *pattern );
 
 int main()
 {
 char string[10005], pattern[10005];
 while(1) {
 scanf("%s", &*string);
 if ( string[0] == '#' && !string[1] ) break;
 scanf("%s", &*pattern);
 printf("%d\n",kmp(string,pattern));
 }
 return 0;
 }
 
 void get_next( char *s )
 {
 int i = 0, j = -1;
 next[0] = -1;
 while ( s[i] ) {
 if ( j== -1 || s[i] == s[j] )
 next[++i] = ++j;
 else
 j = next[j];
 }
 }
 
 int kmp( char *string, char *pattern )
 {
 int answers = 0;
 get_next( pattern );
 int i = 0, j = 0;
 while ( string[i] ) {
 if ( j == -1 || string[i] == pattern[j] ) {
 i++,j++;
 if ( !pattern[j] ) {
 answers++;
 j = 0;
 }
 }
 else j = next[j];
 }
 return answers;
 }

# Oulipo #

Problem 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

BAPC

AZA

AZAZAZA

VERDI

AVERDXIVYERDIAN

Sample Output

1 3 0

#include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
 const int maxn = 10005;
 int next[maxn];
 int cnt;
 char string[10005], pattern[10005];
 
 void get_next( int len2 );
 int kmp(int len1, int len2 );
 
 int main()
 {
 	int num, len1, len2;
 	scanf("%d",&num);
 	getchar();
 	while ( num-- ) {
 		gets(pattern);
 		gets(string);
 		len1 = strlen(string);
 		len2 = strlen(pattern);
 		cnt = 0;
 		kmp(len1,len2);
 		printf("%d\n",cnt);
 	}
 	return 0;
 }
 
 void get_next( int len2 )
 {
 	int i = 0, j = -1;
 	next[0] = -1;
 	while ( i < len2 ) {
 		if ( j == -1 || pattern[i] == pattern[j] )
 			next[++i] = ++j;
 		else
 			j = next[j];
 	}
 }
 
 int kmp( int len1, int len2 )
 {
 	int i = 0, j = 0;
 	get_next(len2);
 	while ( i < len1 ) {
 		if ( j == -1 || string[i] == pattern[j] ) {
 			++i,++j;
 		}
 		else
 			j = next[j];
 		if ( j == len2 ) {
 			cnt++;
 			j = next[j];
 		}
 	}
 	return 0;
 }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKQ0hFTjEyMjE_size_16_color_FFFFFF_t_70]: /images/20220415/133cd689d950407492e4950672db4366.png