KMP专题训练

相关知识总结

训练题总结

其实 KMP 不需要太明白原理直接套模板就可以水过去大部分基础题，但是最近在做 [kuangbin带你飞]专题十六 KMP&扩展KMP&Manacher 发现考察 nex[] 数组原理的很多，所以在此记录做过的练习题

Number Sequence—KMP模板

题意：给你两个长度分别为 n（1<= N <= 1000000）和 m（1 <= M <= 10000）的序列 a[] 和 b[]，求 b[] 序列在 a[] 序列中出现的首位置，如果没有输出 -1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000005;

int len1,len2;
int tex[N],patt[N];

int nex[N];
void getnex(int str[],int len){
	nex[0]=-1;
	for(int i=1,j=-1;i<len;i++){
		while(j!=-1&&str[i]!=str[j+1])j=nex[j];//不符合回退 
		if(str[i]==str[j+1])j++;//符合前进 
		nex[i]=j;//记录当前位置的最长前缀的最后一个字符的位置 
	}
}

//统计patt在tex中出现的次数
int kmp2(int tex[],int patt[]){
	int cnt=0;
	getnex(patt,len2);
	for(int i=0,j=-1;i<len1;i++){
		while(j!=-1&&tex[i]!=patt[j+1])j=nex[j];
		if(patt[j+1]==tex[i])j++;
		//匹配成功后次数+1，同时j回推继续匹配
		if(j==len2-1)return (i+2-len2);
	}
	return 0;
}

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0);
	int t;cin>>t;
	while(t--){
		cin>>len1>>len2;
		for(int i=0;i<len1;i++)cin>>tex[i];
		for(int i=0;i<len2;i++)cin>>patt[i];
		int flag=kmp2(tex,patt);
		if(flag)cout<<flag<<endl;
		else cout<<-1<<endl;
	}
	return 0;
}

Oulipo—KMP模板题

题意：给出匹配串和模式串，让求出模式串在匹配串中出现了几次（串之间可以重叠）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000005;

char tex[N],patt[N];

int nex[N];
inline void getnex(char str[],int len){
	nex[0]=-1;
	for(int i=1,j=-1;i<len;i++){
		while(j!=-1&&str[i]!=str[j+1])j=nex[j];//不符合回退 
		if(str[i]==str[j+1])j++;//符合前进 
		nex[i]=j;//记录当前位置的最长前缀的最后一个字符的位置 
	}
}

//统计patt在tex中出现的次数
inline int kmp2(char tex[],char patt[]){
	int len1=strlen(tex),len2=strlen(patt),cnt=0;
	getnex(patt,len2);
	for(int i=0,j=-1;i<len1;i++){
		while(j!=-1&&tex[i]!=patt[j+1])j=nex[j];
		if(patt[j+1]==tex[i])j++;
		//匹配成功后次数+1，同时j回推继续匹配
		if(j==len2-1)cnt++,j=nex[j];
	}
	return cnt;
}

signed main()
{
	//ios::sync_with_stdio(false),cin.tie(0);
	int t;scanf("%d",&t);
	while(t--){
		//cin>>patt>>tex;
		scanf("%s%s",&patt,&tex);
		//cout<<kmp2(tex,patt)<<endl;
		printf("%d\n",kmp2(tex,patt));
	}
	//system("pause");
	return 0;
}

剪花布条—KMP模板

题意：给出匹配串和模式串，让求出模式串在匹配串中出现了几次（串之间不可以重叠）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1005;

char tex[N],patt[N];

int nex[N];
void getnex(char str[],int len){
	nex[0]=-1;
	for(int i=1,j=-1;i<len;i++){
		while(j!=-1&&str[i]!=str[j+1])j=nex[j];//不符合回退 
		if(str[i]==str[j+1])j++;//符合前进 
		nex[i]=j;//记录当前位置的最长前缀的最后一个字符的位置 
	}
}

//统计patt在tex中出现的次数
int kmp2(char tex[],char patt[]){
	int len1=strlen(tex),len2=strlen(patt),cnt=0;
	getnex(patt,len2);
	for(int i=0,j=-1;i<len1;i++){
		while(j!=-1&&tex[i]!=patt[j+1])j=nex[j];
		if(patt[j+1]==tex[i])j++;
		//匹配成功后次数+1，同时j回推继续匹配
		if(j==len2-1)cnt++,j=-1;
	}
	return cnt;
}

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0);
	while(cin>>tex&&tex[0]!='#'){
		cin>>patt;
		cout<<kmp2(tex,patt)<<endl;
	}
	//system("pause");
	return 0;
}

Cyclic Nacklace—nex[]求循环节+补充

题意：给你一串字符串，问你至少需要添加多少字符才能使它至少循环两次

思想： 题解1  题解2  简单来说就是发现的一个规律，若串存在它的最小循环节一定满足：字符串的长度减去最后一个字符位置的 nex 值（即前缀长度）。

举个例子可以看出来，比如 abcabcabcabc，next[len]=9,所以 len-next[len] 肯定是 len 的约数，并且此时 len-next[len] 也肯定为最短循环节。也可以这么想，如果可以整除，那么肯定存在最短循环节，因为如果能整除你那么肯定前缀跟后缀字符串存在重叠，并且可以分为n个一样的子字符串。

总结规律如下：

• 如果 len%(len-suffix[len])==0，那么字符串本身存在最小循环节长度为 len-suffix[len]
• • 如果 len%(len-suffix[len])!=0，若是前缀和后缀不重叠一定不存在循环节
  • 如果 len%(len-suffix[len])!=0，若是前缀和后缀重叠但是不能整除说明有残缺部分，不存在循环节

这题问需要最少几个字符来让串本身循环两次及以上，无疑需要补充字符的时候我们选择的循环节长度越小那么需要补充的字符数也就越少了，那么我们先利用上述公式求出假定该字符串本身循环时的最小循环节，然后再看是否整除，整除说明本身就是循环，反之说明需要补充字符

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;

char a[N];
int nex[N];

void getnex(char str[],int len){
    nex[0]=-1;
    for(int i=1,j=-1;i<len;i++){
        while(j!=-1&&str[i]!=str[j+1])j=nex[j];
        if(str[i]==str[j+1])j++;
        nex[i]=j;
    }
}

void solve(){
    cin>>a;
    int n=strlen(a);
    getnex(a,n);

    int len=n-(nex[n-1]+1);//最小循环节长度，注意这里nex求出来的是最长前前缀的末尾元素的瞎下标（从0开始），所以长度是在此基础上+1
    if(n%len==0&&len!=n)cout<<0<<endl;//自身就是循环并且循环>1
    else cout<<len-n%len<<endl;//否则说明还需要补齐最后一个循环
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int t;cin>>t;
    while(t--){
        solve();
    }
    //system("pause");
    return 0;
}

Power Strings—nex[]求循环节

题意：给一个字符串，问这个字符串最多可以由一个子串重复多少次得到

思想：假定该字符串循环先求出最小循环节，然后再看看是不是真的循环，是的话也保证了求出来的次数使最多的

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e7+5;

char a[N];
int nex[N];

void getnex(char str[],int len){
    nex[0]=-1;
    for(int i=1,j=-1;i<len;i++){
        while(j!=-1&&str[i]!=str[j+1])j=nex[j];
        if(str[i]==str[j+1])j++;
        nex[i]=j;
    }
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    while(cin>>a){
        if(a[0]=='.')break;
        int n=strlen(a);
        getnex(a,n);

        int len=n-(nex[n-1]+1);//最小循环节长度
        if(n%len==0)cout<<n/len<<endl;//判断是不是真的循环
        else cout<<1<<endl;
    }
    return 0;
}

Period—nex[]求循环节

题意：给你一个字符串，求这个字符串到第 i 个字符为止的循环节的最大次数

思想：上一道题的进阶题，这次是到找第 i 个字符之前为止的循环节的最大次数，其实就是多了一层循环。把这个字符串遍历一次即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000005;

int n;char s[N];
int nex[N];
void getnex(char str[],int len){
	nex[0]=-1;
	for(int i=1,j=-1;i<len;i++){
		while(j!=-1&&str[i]!=str[j+1])j=nex[j];//不符合回退 
		if(str[i]==str[j+1])j++;//符合前进 
		nex[i]=j;//记录当前位置的最长前缀的最后一个字符的位置 
	}
}

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0);
	int count=1;
	while(cin>>n&&n){
		cin>>s;
		getnex(s,n);
		cout<<"Test case #"<<count++<<endl;
		for(int i=1;i<n;i++){
			if(nex[i]!=-1&&((i+1)%(i-nex[i])==0))
			cout<<i+1<<" "<<(i+1)/(i-nex[i])<<endl;
		}
		cout<<endl;
	}
	//system("pause");
	return 0;
}

Seek the Name, Seek the Fame—nex[]定义考察

题意：找出所给串的所有前缀长度，使得所给串中这个长度的前缀==这个长度的后缀

思路：1~nex[] 求出来的位置组成的串就是满足条件，那么找出所有 nex[] 不为 0 的就可以了

#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1e7+5;

char a[N];
int nex[N],ans[N];

void getnex(char str[],int len){
    nex[0]=-1;
    for(int i=1,j=-1;i<len;i++){
        while(j!=-1&&str[i]!=str[j+1])j=nex[j];
        if(str[i]==str[j+1])j++;
        nex[i]=j;
    }
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    while(cin>>a){
        int len=strlen(a);
        getnex(a,len);
        int tot=0,p=len-1;
        while(p>=0){
            ans[tot++]=nex[p]+1;//记录前后缀相同的串的长度
            p=nex[p];//还可以进一步组成
        }
        for(int i=tot-2;i>=0;i--)//tot-1记录的最后长度为0不用输出
            cout<<ans[i]<<" ";
        cout<<len<<endl;//还有一个就是本身,这个答案nex没有记录
    }
    return 0;
}

Blue Jeans—KMP+暴力枚举

题意：给出一组字符串，找出这组字符串公有的长度最长的子串，如果存在多个选择字典序小的那个子串

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=65;

int m;
int nex[N];
vector<string> vec;

void init(){
    vec.clear();
}

bool cmp(string a,string b){
    return a.length()<b.length();
}

void getnex(string str,int len){
	nex[0]=-1;
	for(int i=1,j=-1;i<len;i++){
		while(j!=-1&&str[i]!=str[j+1])j=nex[j];//不符合回退 
		if(str[i]==str[j+1])j++;//符合前进 
		nex[i]=j;//记录当前位置的最长前缀的最后一个字符的位置 
	}
}

bool kmp(string patt){
    int cnt=0;//统计与其他字符串成功匹配的数量
    int len2=patt.length();
    getnex(patt,len2);
    for(int k=1;k<m;k++){//和vec[1...m-1]的字符串尝试匹配
        string tex=vec[k];
        int len1=tex.length();

        for(int i=0,j=-1;i<len1;i++){
            //如果不匹配
            while(j!=-1&&tex[i]!=patt[j+1])j=nex[j];
            //匹配到了，那么下一个
            if(tex[i]==patt[j+1])j++;
            if(j==len2-1){//匹配成功+1并退出循环
                cnt++;break;
            }
        }
    }
    if(cnt==m-1)return true;//全部匹配成功
    else return false;
}

void solve(){
    //存入并排序,选择长度小的子串作为枚举这样优化了暴力
    cin>>m;
    string s;
    for(int i=0;i<m;i++)
    cin>>s,vec.push_back(s);
    sort(vec.begin(),vec.end(),cmp);//默认的字典序比较不是先看长度

    //枚举第一个串的子串并尝试和其他串匹配
    string tot=vec[0],ans="";//第一个串和答案
    for(int i=0;i<=57;i++){//选取子串左端
        string temp="";
        for(int j=i;j<60;j++){//选取子串右端
            temp+=tot[j];//生成子串
            if(j-i+1<3)continue;//子串长度小于3没必要往下走

            if(kmp(temp)){//匹配成功尝试更新答案 注:string自己重载的比较运算符就是逐位字符按照字典序比较这里不满足比较要求
                if(temp.length()>ans.length())ans=temp;//先比长度
                else if(ans.length()==temp.length()&&temp<ans)ans=temp;//长度相同选择字典序小的
            }
        }
    }
    if(ans=="")cout<<"no significant commonalities"<<endl;
    else cout<<ans<<endl;
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int t;cin>>t;
    while(t--){
        init();
        solve();
    }
    return 0;
}

Simpsons’ Hidden Talents—KMP+思维

题意：给两个字符串 str1 和 str2, 求出是 str1 的前缀且是 str2 的后缀的最长的字符串

思想：将两个串和并，然后求一遍nex[] 就可以了，然后取 nex[] 中值大的那个，但是需要注意的是前后缀都不能超过 str1 和 str2 的本身长度，所以需要特判一下能否取值

#include<iostream>
using namespace std;
const int N=1e5+5;

//找a前缀正好是b后缀组成的最大字符串,那就合并然后求nex[lent-1],注意一下就是前后缀长度不能所处字符串本身的长度
string a,b;
int nex[N];

inline void getnex(string str,int len){
	nex[0]=-1;
	for(int i=1,j=-1;i<len;i++){
		while(j!=-1&&str[i]!=str[j+1])j=nex[j];//不符合回退 
		if(str[i]==str[j+1])j++;//符合前进 
		nex[i]=j;//记录当前位置的最长前缀的最后一个字符的位置 
	}
}

inline void solve(){
    int lena=a.length(),lenb=b.length();
    string temp=a+b;
    int lent=lena+lenb;
    getnex(temp,lent);
    int ans=nex[lent-1]+1;

    if(ans==0){//特判
        cout<<0<<endl;
        return ;
    }
    if(ans>lena||ans>lenb)ans=min(lena,lenb);//可能大于其中一个也可能两个都大，所以干脆超出其中一个字符串长度就直接取小的那个
    
    //输出答案
    for(int i=0;i<ans;i++)
    cout<<temp[i];
    cout<<" "<<ans<<endl;
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    while(cin>>a>>b){
        solve();
    }
    return 0;
}