KMP算法的next和nextval数组解析

小咪咪 2022-04-10 08:29 201阅读 0赞

next的代码：

void rnext(string s){
    	next[0]=-1;
    	for(int i=1;i<s.size();i++){
    		int t=i-1;//next[i]存储i之前的最大相同的前缀后缀长度 
    		while(1){
    			if(!t)break;
    			bool flag = true;
    			for(int v=0;v<t;v++){
    				if(s[v]!=s[i-t+v]){
    					flag=false;
    					t--;
    					break;
    				}
    			}
    			if(flag)break;
    		}
    		next[i]=t; 
    	}
    	//for(int i=0;i<s.size();i++)cout<<next[i]<<" ";
    }//得到next数组a b a a b c a c   -1 0 0 1 1 2 0 1

nextval的代码：

void rnextval(string s){
    	nextval[0]=-1;
    	for(int i=1;i<s.size();i++){
    		int t=next[i];
    		if(s[i]==s[t]){
    			nextval[i]=min(nextval[t],next[t]);
    		}else {
    			nextval[i]=next[i];
    		}
    	}
    	for(int i=0;i<s.size();i++)cout<<nextval[i]<<" ";
    }//abaabcac   -1 0 -1 1 0 2-1 1

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpemlfZ2hx_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpemlfZ2hx_size_16_color_FFFFFF_t_70 1][]

附例题：

[https://vjudge.net/problem/POJ-3461][https_vjudge.net_problem_POJ-3461]

附例题代码（最下侧有代码注释，简单易懂）

#include<bits/stdc++.h>
    #include<string>
    using namespace std;
    int next[10005];
    void rnext(string s){
    	next[0]=-1;
    	for(int i=1;i<s.size();i++){
    		int t=i-1;//next[i]存储i之前的最大相同的前缀后缀长度 
    		while(1){
    			if(!t)break;
    			bool flag = true;
    			for(int v=0;v<t;v++){
    				if(s[v]!=s[i-t+v]){
    					flag=false;
    					t--;
    					break;
    				}
    			}
    			if(flag)break;
    		}
    		next[i]=t; 
    	}
    	//for(int i=0;i<s.size();i++)cout<<next[i]<<" ";
    }//得到next数组a b a a b c a c   -1 0 0 1 1 2 0 1  
    int main(){
    	int t,num=0,index;
    	string w;
    	string s;
    	getline(cin,w);
    	rnext(w); 
    	getline(cin,s);
    	int n=s.size(),m=w.size()-1;
    	int j=0;
    	for(int i=0;i<n;){
    		if(s[i]==w[j]){
    			if(j==m){
    				num++;
    				if(m!=0)
    					j=next[j];
    			}else{
    				j++;
    				i++;
    			}
    		}else{
    			if(j==0){
    				i++;
    			}else{
    				j=next[j];
    			}
    		}
    	}
    	cout<<num;
    	return 0;
    }
    //
    //i一直加 如果是和w[0]匹配  w[1] 和i+1比 
    //		如果和w[0]不匹配  w[0] 和i+1比
    //		如果和w[j]匹配    
    //		 	如果j=len   sum++; 和w[next[j]]比， 
    //			如果 j!=len w[j+1]和i+1;  
    //		如果和w[j]不匹配  和w[next[j]]比，直到和w[0]比( w[0] 和i+1比较)

附大佬讲KMP算法（阅读量好几万，简单易懂）：[https://blog.csdn.net/x\_\_1998/article/details/79951598][https_blog.csdn.net_x_1998_article_details_79951598]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpemlfZ2hx_size_16_color_FFFFFF_t_70]: /images/20220401/2d53bf76cd9a4111b4488b036966f156.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpemlfZ2hx_size_16_color_FFFFFF_t_70 1]: /images/20220401/372524112f2547d2be22275bb4510314.png
[https_vjudge.net_problem_POJ-3461]: https://vjudge.net/problem/POJ-3461
[https_blog.csdn.net_x_1998_article_details_79951598]: https://blog.csdn.net/x__1998/article/details/79951598