KMP例题

我会带着你远行 2023-02-09 13:12 10阅读 0赞

KMP算法：实现两个字符串的匹配。  
[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链接][KMP]

##### 例一：子串 #####

[牛客题目链接][Link 1]  
给出一个正整数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 ####

[牛客题目链接][Link 2]  
题意：输入多个字符串，挑选两个字符串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;
    }

#### 例三：\[水\] 悠悠碧波 ####

[牛客测试平台][Link 3]  
题目描述  
帕秋莉掌握了一种水属性魔法  
这种魔法可以净化黑暗  
帕秋莉发现对于一个黑暗的咒语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;
    }

希望将自己的学习经验分享给有需要的人。  
我是小郑，一个不怎么会的小白

[KMP]: https://ethsonliu.com/2018/04/kmp.html
[Link 1]: https://ac.nowcoder.com/acm/problem/13253
[Link 2]: https://ac.nowcoder.com/acm/problem/15489
[Link 3]: https://ac.nowcoder.com/acm/problem/53679