时间戳

首页 > 技术文章 > kmp学习小结

kmp学习小结

jklover 2018-12-28 18:44 原文

KMP

简要说明

  • \(kmp\)是一个非常神奇的东西.它的\(fail(next)\)数组\(f[i]\)就表示\(1\)~\(i\)这个串的最长公共前缀后缀长度.根据这个\(fail\)数组,在匹配的时候就可以加快当前匹配位置的转移,省去一些不必要的比较.

题目

剪花布条

  • 题意:给两个字符串\(s\),\(t\),问将\(s\)按照适当的方式切割后,最多能得到几个串\(t\)?
  • 这里考虑不使用\(hash\)的做法.
  • 在字符串\(s\)中找\(t\),用\(kmp\)即可.需要注意的是前后两次的串不能相交,因为两者不能被同时取到.
  • 匹配的同时记录一下上一个匹配位置即可.\(kmp\)中,若\(j=|t|\),那么此时的\(i\)恰好为这组匹配的起点.
View code 

#include"bits/stdc++.h"
using namespace std;
typedef long long LoveLive;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		{
			fh=-1;
			jp=getchar();
		}
	while (jp>='0'&&jp<='9')
		{
			out=out*10+jp-'0';
			jp=getchar();
		}
	return out*fh;
}
const int MAXN=1e3+10;
char s[MAXN],t[MAXN];
int f[MAXN];
int n,m;
int main()
{
	while(~scanf("%s",s) && (strlen(s)>1 || s[0]!='#') )
		{
			int lspos=-0x7fffffff;
			scanf("%s",t);
			n=strlen(s);
			m=strlen(t);
			int ans=0;
			f[0]=f[1]=0;
			for(int i=1;i=lspos)
						{
							lspos=i;
							++ans;
						}
				}
			printf("%d\n",ans);
		}
	return 0;
}

Power Strings

  • 题意:求一个字符串的最短循环节长度.
  • 这里考虑不使用\(hash\)的做法.
  • 结论:最小循环节长度为\(\frac{n}{n-fail[n]}\),若其为整数.否则为\(|S|\).
  • 证明?不会.建议感性理解或移步此处.
View code 

#include
using namespace std;
typedef long long LoveLive;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		{
			fh=-1;
			jp=getchar();
		}
	while (jp>='0'&&jp<='9')
		{
			out=out*10+jp-'0';
			jp=getchar();
		}
	return out*fh;
}
const int MAXN=1e6+10;
int f[MAXN],n;
char s[MAXN];
void getfail()
{
	f[0]=f[1]=0;
	for(int i=1;i

Radio Transmission

  • 题意:求一个字符串的最短循环节长度.最后一段可以为循环节的前缀.如\(cabcabca\)的最短循环节可以被定义为\(cab\).
  • 这里考虑不使用\(hash\)的做法.
  • 结论:这种定义下的最短循环节长度为\(n-fail[n]\).
  • 感性证明:去掉这个长度为\(fail[n]\)的后缀后,前面的串已经找不到严格意义的循环节.否则可以拼接在\(fail[n]\)对应的公共前后缀上,使\(fail[n]\)增大.此时将前面所有字符作为一个循环节.去掉的部分一定是这个循环节的前缀,满足定义的要求.
View code 

#include"bits/stdc++.h"
using namespace std;
typedef long long LoveLive;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		{
			fh=-1;
			jp=getchar();
		}
	while (jp>='0'&&jp<='9')
		{
			out=out*10+jp-'0';
			jp=getchar();
		}
	return out*fh;
}
const int MAXN=1e6+10;
char s[MAXN];
int f[MAXN];
int main()
{
	int n=read();
	scanf("%s",s);	
	f[0]=f[1]=0;
	for(int i=1;i

OKR-Periods of Words

  • 题意:定义一个串的\(proper\)前缀为它的非空且不等于自身的前缀.定义一个串\(A\)的周期为\(Q\),当且仅当\(Q\)为\(A\)的\(proper\)前缀,且\(A\)为\(QQ\)的前缀.求出一个串所有前缀的最大周期长度和.
  • 只需要沿着\(fail\)指针(失配边)往前跳,跳到第一个不为\(0\)的位置即可,
  • 可以路径压缩进行优化.
View code 

#include"bits/stdc++.h"
using namespace std;
typedef long long LoveLive;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		{
			fh=-1;
			jp=getchar();
		}
	while (jp>='0'&&jp<='9')
		{
			out=out*10+jp-'0';
			jp=getchar();
		}
	return out*fh;
}
const int MAXN=1e6+10;
char s[MAXN];
int n;
int f[MAXN];
int main()
{
	n=read();
	scanf("%s",s);
	f[0]=f[1]=0;
	for(int i=1;i

似乎在梦中见过的样子

  • 题意:在一个字符串中,规定一个形如 \(A+B+A\) 的子串是特殊的,其中有\(|A|\geq k,|B|\geq 1\).给定一个字符串 \(S\) 和常数 \(k\) ,求出 \(S\) 特殊的子串数目.\(|S|\leq 1.5*10^4.\)
  • 此题的数据范围 \(n^2\) 刚好够卡过去.人,要有信仰.
  • 暂时不知道有没有更优秀的做法,但 \(n^2\) 的做法的确是相当无脑的.
  • 枚举特殊子串的左端点 \(x\) ,求出以 \(x\) 为首的后缀的 \(fail\) 数组.计算的时候注意细节,要满足当前的公共前后缀长度大于 \(k\) ,且小于这个串的一半,保证 \(|B|\geq 1\).
View code 

#include"bits/stdc++.h"
using namespace std;
typedef long long LoveLive;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		{
			fh=-1;
			jp=getchar();
		}
	while (jp>='0'&&jp<='9')
		{
			out=out*10+jp-'0';
			jp=getchar();
		}
	return out*fh;
}
const int MAXN=1.5e4+10;
char s[MAXN];
int n,k;
int ans=0;
int f[MAXN];
void kmp(int x)
{
	for(int i=1;i<=n;++i)
		f[i]=x-1;
	for(int i=x+1;i<=n;++i)
		{
			int j=f[i-1];
			while(j!=x-1 && s[i]!=s[j+1])
				j=f[j];
			if(s[i]==s[j+1])
				++j;
			f[i]=j;
		}
	int j=f[n];
	for(int i=x+1;i<=n;++i)
		{
			while(j!=x-1 && s[i]!=s[j+1])
				j=f[j];
			if(s[i]==s[j+1])
				++j;
			while((j-x+1)*2>=(i-x+1))
				j=f[j];
			if(j-x+1>=k)
				++ans;
		}
}
int main()
{
	scanf("%s",s+1);
	k=read();
	n=strlen(s+1);
	for(int i=1;i<=n;++i)
		kmp(i);
	printf("%d\n",ans);
	return 0;
}

Censoring

  • 题意:给出两个字符串 \(S\) 和 \(T\),每次从前往后找到 \(S\) 中的一个 \(T\) 并将其删除,空缺位依次向前补齐,直到 \(S\) 串中不含 \(T\) 串.求最终的 \(S\) 串.
  • 用栈维护串\(S\),匹配成功时从栈顶开始删除.因为要删除多个,所以要用手写的栈.
  • 匹配的过程可以用\(kmp\)或\(hash\)进行优化.
View code 

#include"bits/stdc++.h"
using namespace std;
typedef long long LoveLive;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		{
			fh=-1;
			jp=getchar();
		}
	while (jp>='0'&&jp<='9')
		{
			out=out*10+jp-'0';
			jp=getchar();
		}
	return out*fh;
}
const int MAXN=1e6+10;
char s[MAXN],t[MAXN];
char stk[MAXN];
int tp=0;
int f[MAXN],g[MAXN];
int n,m;
int main()
{
	scanf("%s",s+1);
	scanf("%s",t+1);
	n=strlen(s+1);
	m=strlen(t+1);
	f[0]=f[1]=0;
	int j=0;
	for(int i=2;i<=m;++i)
		{
			while(j && t[i]!=t[j+1])
				j=f[j];
			if(t[j+1]==t[i])
				++j;
			f[i]=j;
		}
	for(int i=1;i<=n;++i)
		{
			stk[++tp]=s[i];
			while(j && t[j+1]!=stk[tp])
				j=f[j];
			if(t[j+1]==stk[tp])
				++j;
			g[tp]=j;
			if(g[tp]==m)
				tp-=m,j=g[tp];
		}
	for(int i=1;i<=tp;++i)
		putchar(stk[i]);
	puts("");
	return 0;
}

推荐阅读