KMP算法:实现两个字符串的匹配。
KMP讲解
//KMP模板
#include<bits/stdc++.h>
using namespace std;
void get_next(string t, int* next){
int i=0;
int j=-1;
next[0]=-1;
while(i<t.length()){
if(j==-1||t[i]==t[j]){
i++,j++;
next[i]=j;
}
else{
j=next[j];
}
}
}
int kmp(string s, string t){
int next[t.length()+5];
get_next(t, next);
int i=0;
int j=0;
while(i<s.length()&&j<t.length()){
if(j==0||s[i]==t[j]){
i++,j++;
}
else{
j=next[j];
}
}
if(i==s.length()){
return -1;
}
if(j==t.length()){
return i-t.length()+1;
}
}
int main(){
string a, b;
a="abcde";
b="cd";
cout<<kmp(a, b);
return 0;
}
推荐学习KMP链接
例一:子串
牛客题目链接
给出一个正整数n,我们把1…n在k进制下的表示连起来记为s(n,k),例如s(16,16)=123456789ABCDEF10, s(5,2)=11011100101。现在对于给定的n和字符串t,我们想知道是否存在一个k(2 ≤ k ≤ 16),使得t是s(n,k)的子串。
输入描述:
第一行一个整数n(1 ≤ n ≤ 50,000)。
第二行一个字符串t(长度 ≤ 1,000,000)
输出描述:
“yes"表示存在满足条件的k,否则输出"no”
示例1
输入
8
01112
输出
yes
这道题直接套KMP模板就行,没有太多拐弯抹角的东西。
#include<bits/stdc++.h>
using namespace std;
char jz[18]="0123456789ABCDEF";
string t, s="";
void zh(int n, int k){
string ss;
while(n>0){
if(n%k!=0){
ss+=jz[n%k];
}
else ss+=jz[0];
n/=k;
}
reverse(ss.begin(), ss.end());
s += ss;
}
void get_next(string t, int*next){
int i=0;
int j=-1;
next[0]=-1;
while(i<=t.length()){
if(t[i]==t[j]||j==-1){
j++, i++;
next[i]=j;
}
else{
j=next[j];
}
}
}
bool kmp(string s, string t){
int next[t.length()+5];
get_next(t, next);
int i=0;
int j=0;
while(j<t.length() && i<s.length()){
if(t[j]==s[i]||j==0){
j++, i++;
}
else{
j = next[j];
}
}
if(j==t.length()){
return true;
}
return false;
}
int main()
{
int N;
cin>>N>>t;
for(int k=2; k<=16; k++){
s="";
for(int n=1; n<=N; n++){
zh(n, k);
}
// cout<<s<<endl;
if(kmp(s, t)){
cout<<"yes";
return 0;
}
}
cout<<"no";
return 0;
}
例二:Youhane Assembler
牛客题目链接
题意:输入多个字符串,挑选两个字符串s1,s2。
判断s1的后缀字母与s2的前缀字母有多少个字符能匹配。
eg:s1=“ABCDE” s2=“CDEFG”
ps:它们能匹配的字符有3个为"CDE"。
eg: s1=“CDEFG” s2=“ABCDE”
ps:它们能匹配的字符有0个,因为s2字符串中没有G。
运用KMP特性
在KMP里我们了解到,next数组能够将一个字符串前后缀进行匹配,从而达到避免字符串匹配的时候重复判断的效果。
在题目中,我们可以利用next数组匹配字符串前后缀的功能来实现s1与s2的匹配。
解题分析
①、将s1与s2结合为一个字符串s
s=s2+"#"+s1
(ps:s2要前缀,s1要后缀,在中间加上"#"防止s2与s1“越界匹配”)
②、判断字符串s的前缀与后缀有ans个字符能匹配成功。
ans = next[s.length()]
#include<bits/stdc++.h>
using namespace std;
string str[300005];
void get_next(string s, int * next){
int i=0;
int j=-1;
next[0]=-1;
while(i<s.length()){
if(s[i]==s[j]||j==-1){
i++, j++;
next[i]=j;
}
else{
j = next[j];
}
}
}
int main()
{
int n;
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1; i<=n; i++)
cin>>str[i];
int m;
cin>>m;
for(int i=1; i<=m; i++){
int q1, q2;
cin>>q1>>q2;
string s = str[q2]+"#"+str[q1];
int len=s.length();
if(q1==q2){
cout<<str[q1].length()<<endl;
}
else{
int next[s.length()+5];
get_next(s, next);
cout<<next[len]<<endl;
}
}
return 0;
}
例三:[水] 悠悠碧波
牛客测试平台
题目描述
帕秋莉掌握了一种水属性魔法
这种魔法可以净化黑暗
帕秋莉发现对于一个黑暗的咒语s,可以使用这个水元素魔法净化它,净化的咒语是一个最长的字符串t,t满足以下条件:
它是s的前缀
它是s的后缀
除前缀和后缀外,它还在s中出现过至少一次
既然你都学会了,那么净化的工作就交给你了!
输入描述:
一行字符串 s 代表黑暗咒语
输出描述:
一个字符串 t 表示满足条件的最长净化咒语
示例1
输入
tqrwantoacthisproblembutqristooweaktodoitqr
输出
tqr
备注:
对于60%的数据,s长度≤100
对于100%的数据,s长度≤100,000
保证存在可行的净化咒语
注意:前后缀不可重叠
不能直接利用 next 函数进行前后缀是否相等的判断,这里我用双指针(l,r)的方式进行前后缀是否相等的判断。
l : 指向前缀的结尾字符下标
r : 指向后缀的开头字符下标
解题步骤
初始化:l =0, r=s.length()-1
1、确定 t 串条件
限制条件:
排除大部分多余情况
①、前缀与后缀长度相等
②、前缀的结尾字符 == s 的结尾字符(s[l] == s[s.length()-1])
③、后缀的开头字符 == s 的开头字符(s[r] == s[0])
最终确定
①、前缀与后缀完全相等
②、利用 kmp 判断字符串 s 在下标为 l+1 ~ r-1 的范围内有无与前缀相同的串
2、若满足1内所有条件则将下标 l 保存
3、试探有没有更大的字符串符合条件
4、若 l>=r ,输出字符串 s 的前缀下标为 0 ~ l ,结束程序。否则将 l++,回到步骤1
以上解题步骤还有一些优化的空间,例如 l < r可以改为 l < s.length()/3,有兴趣的朋友可以接着优化。
#include<bits/stdc++.h>
using namespace std;
string s;
void get_next(string T, int*next){
int i=0, j=-1;
next[0]=-1;
while(i<T.length()){
if(T[i]==T[j]||j==-1){
j++;
i++;
next[i]=j;
}
else
j = next[j];
}
return ;
}
bool kmp(int begin, int end, string s, string T){
int next[100010];
get_next(T, next);
int i=begin, j=0;
while(i<=end&&j<T.length()){
if(s[i]==T[j]||j==0){
i++,j++;
}
else{
j = next[j];
}
}
if(j==T.length()) return true;
else return false;
}
int main(){
cin>>s;
int l=0, r=s.length()-1, ans=0, l_len, r_len;
char L=s[l], R=s[r];
while(L!=s[r]) r--;
while(R!=s[l]) l++;
while(l<r){
l_len = l+1;
r_len = s.length() - r;
while(l_len!=r_len){
if(L!=s[r] || R!=s[l]){
while(L!=s[r]&&l<r) r--; //将前缀的开头字母与后缀的开头字母配对
while(R!=s[l]&&l<r) l++; //将后缀的结尾字母与前缀的结尾字母配对
}
else if(l_len>r_len){
r--;
}
else{
l++;
}
l_len = l+1;
r_len = s.length() - r;
}
string T = s.substr(0, l+1), t = s.substr(r);
//保证前后缀相同,同时在中间找与前后缀相同的串
if(T==t&&kmp(l+1, r-1, s, T))
ans = l+1;
//试探有没有更长字符串
l++, r--;
while(R!=s[l]) l++;
while(L!=s[r]) r--;
}
cout<<s.substr(0, ans);
return 0;
}
希望将自己的学习经验分享给有需要的人。
我是小郑,一个不怎么会的小白