KMP专题总结

首页 > 代码库 > KMP专题总结

2024-07-16 17:04:30 223人阅读

KMP算法有两种计算失配函数的方法

未优化过的失配函数， f[i] 就表示 str[0~i-1] 的公共最长前后缀( 不包括str[0~i-1]本身，比如aaa的最长公共前后缀长度为2 ) ，这个特性必须牢记

从下面的例子应该也可以看出

0 1 2 3 4 5 6 7 8 9 10

str a a a a b b a a b a ‘\0’

f 0 0 1 2 3 0 0 1 2 0 1

优化过后的失配函数，虽然匹配的性能要好点，不过失去上述这么优美的特性，基本也就是废了( 应该不至于出道裸的匹配，然后卡失配函数吧 )

=========================================我是分割线=================================================

模板和原理我就不赘述了，网上资料很多，贴个模板完事

未优化的失配函数

void get_nex( char * str ){
	int len = strlen( str ) ;
	f[0] = 0 , f[1] = 0 ;
	for( int i = 1 ; i < len ; i ++ ) {
		int j = f[i] ;
		while( j && str[i] != str[j] ) j = f[j] ;
		// 跟某个前缀匹配成功,那么下次从下个前缀可以匹配
		if( str[i] == str[j] ) f[i+1] = j + 1 ;
		// 否则从头开始匹配
		else f[i+1] = 0 ;
	}
}

KMP 匹配函数

int KMP( char * str , char * sub_str ) {
	int len1 = strlen( str ) , len2 = strlen( sub_str ) ;
	// 当前跟子串的那个字符匹配
	int j = 0 ;
	int ans = 0 ;
	for( int i = 0 ; i < len1 ; i ++ ) {
		// 如果成功下次匹配下一个字符 , 否则一直沿失配边走 
		while( j && str[i] != sub_str[j] ) j = f[j] ;
		if( str[i] == sub_str[j] ) j ++ ;
		if( j == len2 ) j = f[j] , ans ++ ;
	}
	return ans ;
}

=====================================我是华丽丽的分割线==============================================

比较常见的问题 ( 应该要熟练掌握 ) :

1. KMP 求出 S[0...i-1] 的所有的公共前后缀的问题

这个东西在某些题目中会用于统计

很显然 , f[i] 的值就是 S[0...i-1] 的最长公共前后缀 ( 还是一样不包括串本身的 )，因为那个华丽丽的特性

然后怎么求稍微短一点的 ? 仔细一想，s[0...i-1] 次长( 存在的话 ) 的公共前后缀，就是 s[0...i-1] 和 s[i-f[i],i-1] 的最长公共前后缀。

那么又因为s[i-f[i],i-1] 本身就是原串是 s[0,f[i]-1] , 所以次长的公共前后缀就是 f[f[i]] 了

后面的就以此类推就行

2. KMP 求循环串

什么是循环串就是某个字符串可以由它的前缀重复几次得到这个串本身。比如 aabaabaabaab ，可以有 aab ， aabaab ， aabaabaabaab 循环得出

假设我们称 aab , aabaab 这样的为循环节

那么怎么求最长的循环节呢 ? len - f[len] 就是循环节的长度，当然要同时满足 len % ( len - f[len] ) == 0

假设字符串的长度为 len ，len - f[len] = K , K * t = len

那么根据上述结论，整个字符串就应该是由 t 个 s[0...K-1] 循环组成的，如何得到这个呢 ?

S[0...K-1] , S[K,2*K-1] ...................... S[(t-1)*K,t*K-1 ]

S[0,K-1] , S[K,2*K-1] ..... S[(t-2)*K,(t-1)*K-1] , S[(t-1)*K,t*K-1]

因为我们知道 f[len] = len - K , 也就是说字符串的前 ( t-1) * K 个字符串和后( t - 1 ) * K 个字符串的相等的

那么我们就可以得到 S[0,K-1] == S[K,2*K-1] .... S[(t-1)*K,t*K-1] = S[(t-2)*K,(t-1)*K-1]

所以我们很容易得到 S[0,K-1] == S[K,2*K-1] = ... = S[(t-1)*K,t*K-1]

OK，我们已经得到答案了

至于再大一点的循环节，我们只要求小一点的最长公共前后缀就行了。

=====================================又是华丽丽的分割线==============================================

KMP题目 :

POJ 3461 Oulipo

POJ 1019 Number Sequence

两道模板题 ...

POJ 2406 Power Strings

求最短的循环节的循环次数

上面已经说过了，直接 len / (len - f[len]) 用这个公式就行

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 1000005

char str[MAXN] ;
int f[MAXN] ;

void get_nex( char * str ) {
	int len = strlen( str ) ;
	int j; 
	f[0] = f[1] = 0 ;
	for( int i = 1 ; i < len ; i ++ ) {
		j = f[i] ;
		while( j && str[i] != str[j] ) j = f[j] ;
		if( str[i] == str[j] ) f[i+1] = j + 1 ;
		else f[i+1] = 0 ;
	}
}

int main(){
	while( scanf( "%s" , str ) != EOF ) {
		if( strcmp( "." , str ) == 0 ) break;
		get_nex( str ) ;
		int len = strlen( str ) ;
		if( len % ( len - f[len] ) == 0 ) {
			printf( "%d\n" , len / ( len - f[len] ) ) ;
		}else{
			printf( "1\n" ) ;
		}
	}
	return 0 ;
}

HDOJ 3336 Count the string

求各个前缀在字符串中出现的次数的总和

dp[i] 表示以字符i-1为结尾的和前缀相同的子串的有多少

那么 : dp[i] = dp[f[i]] + 1 , 首先以为结尾的字符串本身肯定是一个前缀，所以至少是1

然后dp[f[i]] 是以 f[i] -1 为结尾的前缀数，而s[0~f[i]-1]又刚好就是s[0~i-1]的后缀，所以第i-1个字符结尾的长度小于i的字符串总数为dp[f[i]]

最后求个和就行了

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define mod 10007

char str[200005] ;
int    f[200005] ;
int   dp[200005] ;

void get_nex( char * str , int len ){
	f[0] = f[1] = 0 ;
	int j ;
	for( int i = 1 ; i < len ; i ++ ) {
		j = f[i] ;
		while( j && str[i] != str[j] ) j = f[j] ;
		if( str[i] == str[j] ) f[i+1] = j + 1 ;
		else f[i+1] = 0 ;
	}
}

int main(){
	int cas ;
	scanf( "%d" , &cas ) ;
	while( cas -- ) {
		int len ;
		scanf( "%d" , &len ) ;
		scanf( "%s" , str ) ;
		get_nex( str , len );
		dp[1] = 1 ;
		int sum = 1 ;
		for( int i = 2 ; i <= len ; i ++ ) {
			dp[i] = dp[f[i]] + 1 ;
			sum += dp[i] ;
			sum %= mod ;
		}
		printf( "%d\n" , sum ) ;
	}
	return 0 ;
}

HDOJ 3336 Theme Section

求既是字符串的前缀，又是字符串的后缀，又在中间出现的最长子串( 三个不能重叠 ) 。

首先我们要求出所有既是前缀又是后缀的字符串的长度，用vis数组标记下

然后枚举中间的字符串的终点，求出 f[i] 在判断下合不合法，有没有标记过

最后求出长度最大，既合法，又被vis数组标记过的长度就行了

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define MAXN 1000005

char str[MAXN] ;
int  f[MAXN] ;
bool vis[MAXN] ;

void get_nex( char * str , int len ) {
	f[0] = f[1] = 0 ;
	int j ;
	for( int i = 1 ; i < len ; i ++ ) {
		j = f[i] ;
		while( j && str[i] != str[j] ) j = f[j] ;
		if( str[i] == str[j] ) f[i+1] = j + 1 ;
		else f[i+1] = j ;
	}
}

int main(){
	int cas ;
	scanf( "%d" , &cas ) ;
	while( cas -- ) {
		scanf( "%s" , str ) ;
		int len = strlen( str ) ;
		memset( vis , false , sizeof(vis) ) ;
		get_nex( str , len ) ;
		int Len = f[len] ;
		while( Len ) {
			vis[Len] = true ;
			Len = f[Len] ;
		}
		int ans = 0 ;
		for( int i = 2 ; i < len ; i ++ ) {
			int ll = f[i] ;
			int tmp = min( min( ll , i / 2 ) , min( f[len] , len - i ) ) ;
			if( vis[tmp] ) ans = max( ans , tmp ) ;
		}
		printf( "%d\n" , ans ) ;
	}
	return 0 ;	
}

POJ 2185 Milking Grid

就是求二维情况的循环串

我是先把一维用多项式hash压缩掉，求一维的循环节，然后在压缩另外一维，再求一遍就行了

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std ;

#define MAXN 10005
char mp[MAXN][85] ;
typedef unsigned __int64 uLL ;
uLL a[MAXN] ;
int f[MAXN] ;

void get_nex( uLL * a , int len ){
	f[0] = 0 , f[1] = 0 ;
	int j ;
	for( int i = 1 ; i < len ; i ++ ) {
		j = f[i] ;
		while( j && a[i] != a[j] ) j = f[j] ;
		if( a[i] == a[j] ) f[i+1] = j + 1 ;
		else f[i+1] = 0 ;
	}
}

int main(){
	int n , m ;
	while( scanf( "%d%d" , &n,  &m ) != EOF ) {
		for( int i = 0 ; i < n ; i ++ ) {
			scanf( "%s" , mp[i] ) ;
			a[i] = 0 ;
			for( int j = 0 ; j < m ; j ++ ) {
				a[i] = a[i] * 10007 + mp[i][j] - 'A' ;				
			}
		}
		get_nex( a , n ) ;
		int H = n - f[n] ;
		for( int i = 0 ; i < m ; i ++ ) {
			a[i] = 0 ;
			for( int j = 0 ; j < H ; j ++ ) {
				a[i] = a[i] * 10007 + mp[j][i] - 'A' ;
			}
		}
		get_nex( a , m ) ;
		int W = m - f[m] ;
		printf( "%d\n" , H * W ) ;
	}
	return 0 ;
}

HDOJ 2594 Simpsons’ Hidden Talents

给你两个串，让你求第一串和第二个串的最长公共前后缀

我直接把两个字符串用#连起来,求下失配函数, f[len]就是要求的答案了

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define MAXN 50005 * 2 
char str[MAXN] ;
int f[MAXN] ;

void get_nex( char * str , int len ){
	f[0] = f[1] = 0 ;
	int j ;
	for( int i = 1 ; i < len ; i ++ ) {
		j = f[i] ;
		while( j && str[i] != str[j] ) j = f[j] ;
		if( str[i] == str[j] ) f[i+1] = j + 1 ;
		else f[i+1] = 0 ;
	}
}

int main(){
	while( scanf( "%s" , str ) != EOF ) {
		int len = strlen( str ) ;
		str[len] = '#' ;
		scanf( "%s" , str + len + 1 ) ;
		len = strlen( str ) ;
		get_nex( str , len ) ;
		if( f[len] ) {
			str[f[len]] = 0 ;
			printf( "%s %d\n" , str , f[len] ) ;
		}else{
			printf( "0\n" ) ;
		}
	}
	return 0 ;
}

HDOJ 3746 Cyclic Nacklace

问至少增加一个字符可以变成至少有两个以上循环节的循环串

如果本身就是循环串，如果只有一个循环节，那要在复制一次字符串，否则答案就是0

不是的话，就看 len - f[len] 的长度，看添加几个能补到被len整数就行了

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stack>
using namespace std;

#define MAXN 400005

char str[MAXN] ;
int f[MAXN] ;

void get_nex( char * str , int len ){
	f[1] = f[0] = 0 ;
	int j; 
	for( int i = 1 ; i < len ; i ++ ) {
		j = f[i] ;
		while( j && str[i] != str[j] ) j = f[j] ;
		if( str[i] == str[j] ) f[i+1] = j + 1 ;
		else f[i+1] = 0 ;
	}
}

int main(){
	while( scanf( "%s" , str ) != EOF ) {
		int len = strlen( str ) ;
		get_nex( str , len ) ;
		stack<int> s ;
		s.push( len ) ;
		while( f[len] ) {
			s.push( f[len] ) ;
			len = f[len] ;
		}
		bool first = true ;
		while( !s.empty() ) {
			printf( first?"%d" :" %d" , s.top() ) ;
			s.pop() ;
			first = false ;
		}
		puts( "" ) ;
	}
	return 0 ;
}

POJ 2752 Seek the Name, Seek the Fame

就是求所有的前后缀的长度，从小到大输出来

上面已经讲过了，直接 len , f[len] , f[f[len]] ... 一路到0就行了

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stack>
using namespace std;

#define MAXN 400005

char str[MAXN] ;
int f[MAXN] ;

void get_nex( char * str , int len ){
	f[1] = f[0] = 0 ;
	int j; 
	for( int i = 1 ; i < len ; i ++ ) {
		j = f[i] ;
		while( j && str[i] != str[j] ) j = f[j] ;
		if( str[i] == str[j] ) f[i+1] = j + 1 ;
		else f[i+1] = 0 ;
	}
}

int main(){
	while( scanf( "%s" , str ) != EOF ) {
		int len = strlen( str ) ;
		get_nex( str , len ) ;
		stack<int> s ;
		s.push( len ) ;
		while( f[len] ) {
			s.push( f[len] ) ;
			len = f[len] ;
		}
		bool first = true ;
		while( !s.empty() ) {
			printf( first?"%d" :" %d" , s.top() ) ;
			s.pop() ;
			first = false ;
		}
		puts( "" ) ;
	}
	return 0 ;
}

ZOJ 3587 Marlon‘s String

给你两个字符串，第一个字符串中取出两段来，有多少种方式可以组成第二个字符串。取出来的两段可以重叠

那么我们先统计一下cnt1[i] 表示第一个字符串中有多少子串是第二个字符长度为i的子串

计算的时候我们先根据匹配结果去统计，即到匹配到一次长度为i的就cnt1[i] ++ ; 然后因为s[0...i-1] 出现一次的话，那么s[0...f[i]-1]肯定也要出现一次，所以我们统计到cnt1[i] 的时候，要cnt1[f[i]] += cnt1[i]

当然出现一次 s[0...i-1]更短的也会出现过，但是我们计算到cnt1[i]的时候并不用统计，因为这些会在cnt1[f[i]]统计的时候加上

然后两个字符串反过来在匹配一遍，统计出cnt2[i]

那么最后答案就是Σ( cnt1[i] * cnt2[len-i] ) 了

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define MAXN 100001

typedef long long LL ;

char s[MAXN] ;
char t[MAXN] ;
char tmp[MAXN] ;
int cnt1[MAXN] , cnt2[MAXN] ;
int f[MAXN] ;

void get_nex( char * str , int len ) {
	f[0] = f[1] = 0 ;
	int j ;
	for( int i = 1 ; i < len ; i ++ ) {
		j = f[i] ;
		while( j && str[i] != str[j] ) j = f[j] ;
		if( str[i] == str[j] ) f[i+1] = j + 1 ;
		else f[i+1] = 0 ;
	}
}

void KMP( char * str1 , int len1 , char * str2 , int len2 , int * cnt ) {
	int j = 0 ;
	for( int i = 0 ; i < len1 ; i ++ ) {
		while( j && str1[i]!=str2[j] ) j = f[j] ;
		if( str1[i] == str2[j] ) {
			j ++ ; cnt[j] ++ ;
		}
		if( j == len2 ) j = f[j] ;
	}
}

void stringrev( char * s ) {
	int len = strlen( s ) ;
	strcpy( tmp , s ) ;
	for( int i = 0 ; i < len ; i ++ ) {
		s[len-i-1] = tmp[i] ;
	}
	s[len] = 0 ;
}

int main(){
	int cas ;
	scanf( "%d" , &cas ) ;getchar() ;
	while( cas -- ) {
		gets(s);
		gets(t);
		int len1 , len2 ;
		len1 = strlen( s ) , len2 = strlen( t ) ;
		get_nex( t , len2 ) ;
		memset( cnt1 , 0 ,sizeof(cnt1) ) ;
		KMP( s , len1 , t , len2 , cnt1 ) ;
		for( int i = len2 ; i >= 1 ; i -- ) {
			cnt1[f[i]] += cnt1[i] ;
		}
		stringrev( s ) ;
		stringrev( t ) ;
		get_nex( t , len2 ) ;
		memset( cnt2 , 0 , sizeof(cnt2) ) ;
		KMP( s , len1 , t , len2 , cnt2 ) ;
		for( int i = len2 ; i >= 1 ; i -- ) {
			cnt2[f[i]] += cnt2[i] ;
		}
		LL ans = 0 ;
		for( int i = 1 ; i < len2 ; i ++ ) {
			ans += (LL)cnt1[i] * cnt2[len2-i] ;
		}
		printf( "%lld\n" , ans ) ;
	}
	return 0 ;
}

POJ 3167 Cow Patterns

给你两个序列，要求匹配模式串，怎么算匹配上呢，就是两个区间中各个数的相对名次是一样的

比如a[i]的名次比哪些小，和哪些一样，都要匹配上

我们预处理出每个数前面有几个比它小的和几个小于等于它的，然后改写下字符匹配上的标准就行了

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;

int n , m , s ;
int a[100005] , b[100005] ;
int sa[100005][30] ;
int sb[100005][30] ;
int f[100005] ;

vector<int> ans ;

void get_nex( int * a , int (*p)[30] , int len ){
	f[0] = f[1] = 0 ;
	int j ;
	for( int i = 1 ; i < len ; i++ ) {
		j = f[i] ;
		while( j && ( p[j+1][a[j]] != p[i+1][a[i]] - p[i-j][a[i]] || p[j+1][a[j]-1] != p[i+1][a[i]-1] - p[i-j][a[i]-1] ) ) j = f[j] ;
		if( p[j+1][a[j]] == p[i+1][a[i]] - p[i-j][a[i]] && p[j+1][a[j]-1] == p[i+1][a[i]-1] - p[i-j][a[i]-1] ) f[i+1] = j + 1 ;
		else f[i+1] = 0 ;
	}
}

void KMP( int * a , int (*p)[30] , int len1 , int *b , int (*q)[30] , int len2 ) {
	int j = 0 ;
	for( int i = 0 ; i < len2 ; i ++ ) {
		while( j && ( p[j+1][a[j]] != q[i+1][b[i]] - q[i-j][b[i]] || p[j+1][a[j]-1] != q[i+1][b[i]-1] - q[i-j][b[i]-1] ) ) j = f[j] ;
		if( p[j+1][a[j]] == q[i+1][b[i]] - q[i-j][b[i]] && p[j+1][a[j]-1] == q[i+1][b[i]-1] - q[i-j][b[i]-1] ) j ++ ;
		if( j == len1 ) ans.push_back( i - len1 + 2 ) , j = f[j] ; 
	}
}

int main(){
	while( scanf( "%d%d%d" , &n , &m , &s ) != EOF ) {
		for( int i = 0 ; i < n ; i ++ ) {
			scanf( "%d" , &a[i] ) ;
			sa[i+1][a[i]] ++ ;
			for( int j = 1 ; j <= s ; j ++ ) 
				sa[i+1][j] += sa[i][j] ;
		}
		for( int i = 0 ; i < n ; i ++ ) {
			for( int j = 1 ; j <= s ; j ++ )
				sa[i+1][j] += sa[i+1][j-1] ;
		}
		for( int i = 0 ; i < m ; i ++ ) { 
			scanf( "%d" , &b[i] ) ;
			sb[i+1][b[i]] ++ ;
			for( int j = 1 ; j <= s ; j ++ )
				sb[i+1][j] += sb[i][j] ;
		}
		for( int i = 0 ; i < m ; i ++ ) {
			for( int j = 1 ; j <= s ; j ++ )
				sb[i+1][j] += sb[i+1][j-1] ;
		}
		get_nex( b , sb , m ) ;
		ans.clear() ;
		KMP( b , sb , m , a , sa , n ) ;
		printf( "%d\n" , ans.size() ) ;
		for( int i = 0 ; i < ans.size() ; i ++ ) {
			printf( "%d\n" , ans[i] ) ;
		}
	}
	return 0 ;
}

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > KMP专题总结

KMP专题总结

看完仍有疑问？有类似问题直接问程序猿