KMP及其应用
Nick_zheng
blog
$KMP$ 及其应用
特别声明: 以下仅为个人直观理解, 并不都正确严谨
$KMP$, 一种求(字符串)匹配问题的算法, 但不仅局限于此, 其中蕴含的前缀函数的思想可以在许多字符串甚至推广到一些看似毫无关联的题目中 qaq.
这里先贴出模板(附加个人的直观理解, 不是正规解释, 仅供娱乐 qaq)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
string a,b;
int kmp[N];//next数组, 最长前后缀长度数组
signed main()
{
cin>>a;
cin>>b;
int lena=a.size();
int lenb=b.size();
a=" "+a;
b=" "+b;//下标1开头
int j=0;//子串匹配过的长度
for(int i=2;i<=lenb;i++)//next[1]=0(规定)
{
while(j&&b[i]!=b[j+1])//确保j合法, 且失配
{
j=kmp[j];//跳走继续匹配
}
if(b[i]==b[j+1])//如果可以匹配
{
j++;//则往后移动
}
kmp[i]=j;//此时的j就是next[i]的值
}
j=0;//清零
int cnt=0;
for(int i=1;i<=lena;i++)//直接复制即可, 改几处, 注意这次要从1开始
{
while(j&&a[i]!=b[j+1])
{
j=kmp[j];
}
if(a[i]==b[j+1])
{
j++;
}
if(j==lenb)//子串全部匹配成功
{
printf("%lld\n",i-lenb+1);//i-j+1也可, 求出的位置(此时i为末尾, 要减去j-1)
//处理, 可以做标记/dp等
j=kmp[j];//跳到下一个位置继续匹配
}
}
for(int i=1;i<=lenb;i++)
{
printf("%lld ",kmp[i]);//按要求输出
}
printf("\n");
return 0;
}
好的, 以上就是 $KMP$ 的基础作用 qaq.
下面介绍几个 $tricks$:
1. P4391 [BalticOI 2009] Radio Transmission 无线传输
- 题目简介: 求串 s 的周期
- 这里直接给出结论: $T=n-\text{next}[n]$ (证明: OI-wiki)
- 直观理解:
前缀部分...----**...
后缀部分...**----...
(-表示公共前后缀, *表示其余字符)
标号(一个标号代表一个周期(会推导出), 而非一个字符):
假设有6个周期, 公共前后缀如下
*-----
-----*
123456
abcdef
已知1=a, 且有1~5=b~f, 则可认为1=a=b(公共前后缀等长的部分一定完全相同), 以此类推, 归纳可得我们分的每一段即为一个周期qaq.
然后呢我们就可以得出 T=n-next[n].
至此证毕口胡完成 qaq. 代码显然.
#include<cstdio>
#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N=1e6+10;
int kmp[N];
signed main()
{
int n;
scanf("%lld",&n);
string s;
cin>>s;
s=" "+s;
int j=0;
for(int i=2;i<=n;i++)
{
while(j&&s[i]!=s[j+1])
{
j=kmp[j];
}
if(s[i]==s[j+1])
{
j++;
}
kmp[i]=j;
}
printf("%lld\n",n-kmp[n]);
return 0;
}
扩展到二维: P10475 [USACO03FALL] Milking Grid（数据加强版）
- 很显然我们可以先把一整行哈希成为一个数字编号(看做字符), 然后对这个序列对行求一维的周期 $T_1$, 同理求出列的一维周期 $T_2$, 然后二维的显然就是 $T_1 \times T_2$(
感性理解下), 这里用到了化归和分割子问题再结合的思想, 以及压缩思想的一个简单体现.
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+10,M=1e2;
string s[N];
int a[N],b[N],next1[N],next2[N];
int cnt=0;
map<string,int> mpp;
int mp(string x)
{
if(mpp[x])
{
return mpp[x];
}
return mpp[x]=++cnt;
}
signed main()
{
int r,c;
scanf("%lld %lld",&r,&c);
for(int i=1;i<=r;i++)
{
cin>>s[i];
s[i]=" "+s[i];
}
for(int i=1;i<=c;i++)
{
string t;
for(int j=1;j<=r;j++)
{
t+=s[j][i];
}
a[i]=mp(t);
}
for(int i=1;i<=r;i++)
{
string t;
for(int j=1;j<=c;j++)
{
t+=s[i][j];
}
b[i]=mp(t);
}
for(int i=2,j=0;i<=c;i++)
{
while(j&&a[i]!=a[j+1])
{
j=next1[j];
}
if(a[i]==a[j+1])
{
j++;
}
next1[i]=j;
}
for(int i=2,j=0;i<=r;i++)
{
while(j&&b[i]!=b[j+1])
{
j=next2[j];
}
if(b[i]==b[j+1])
{
j++;
}
next2[i]=j;
}
printf("%lld\n",(c-next1[c])*(r-next2[r]));
return 0;
}