练习题解（关于KMP）

目录

1.【模板】KMP

2. [BOI2009] Radio Transmission 无线传输

3.构造字符串

1.【模板】KMP

原题链接

输入数据：

ABABABC
ABA

既然是KMP算法的模板题，那么做这道题之前需要掌握KMP算法的基础知识，可以看看b站干货

直接给AC代码吧，毕竟模板题。

#include<bits/stdc++.h>
using namespace std;
int len1,len2;
int next1[1000001];
char s1[1000001];
char s2[1000001];
void get_next() //求出next数组 
{ 
    int i=0,j=-1;
    next1[0]=-1;
    while(i<len2) 
        if(j==-1 || s2[i]==s2[j]) 
            next1[++i]=++j;
        else j=next1[j];
} 
void KMP() //KMP 
{ 
    int i=0,j=0;//从第一个元素开始匹配 
    while(i<len1) 
    { 
        if(j==-1 || s1[i]==s2[j]) //匹配成功 
            i++,j++;
        else j=next1[j]; //失配 
        if(j==len2)
		{
			cout<<i-len2+1<<endl;//此时i-len2+1为匹配成功的第一个元素位置 
			j=next1[j];//匹配成功，再失配 
		} 
    }  
} 
int main(){ 
    cin>>s1>>s2;
    len1=strlen(s1);
    len2=strlen(s2);
    get_next();
    KMP();
    for(int i=1;i<=len2;++i) 
        cout<<next1[i]<<" ";//输出next数组 
    return 0;
}

2. [BOI2009] Radio Transmission 无线传输

原题链接

输入数据：

8
cabcabca

这道题需要我们找一个字符串重复自身形成的字符串的子串为我们输入的字符串，并且要求输出这个字符串的长度（最小）。

那我们如何找这个循环串的长度，首先求出next数组来求输入字符串的最长前后缀长度。

就可以推出循环串长度为n（字符串长度）-k（最长相同前后缀长度）。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int nex[1000100];
int main()
{
	int n;
	cin>>n;
	string s;
	cin>>s;
	int i=0,j;
	nex[0]=j=-1;
	while(i<n){
		if(j==-1||s[i]==s[j]) nex[++i]=++j;
		else j=nex[j];//求最长相同前后缀长度 
	}
	cout<<n-nex[n];
	return 0;
}

3.构造字符串

原题链接

输入样例1：

3 4
aba

输出样例1：

ababababa

输入样例2：

3 2
cat

输出样例2：

catcat

这道题和第二题有异曲同工之妙，也是需要我们找出字符串的最长相同前后缀长度n，输出原串，然后重复k-1次输出下标为n后面的子串。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int nex[100];
int main()
{
	int n,k;
	cin>>n>>k;
	string s;
	cin>>s;
	int i=0,j;
	nex[0]=j=-1;
	while(i<n){
		if(j==-1||s[i]==s[j]) nex[++i]=++j;
		else j=nex[j];
	}
	cout<<s;
	for(int i=0;i<k-1;i++){
		cout<<s.substr(nex[n]);
	}
	return 0;
}