当前位置:网站首页>KMP! You deserve it!!! Run directly!

KMP! You deserve it!!! Run directly!

2022-06-11 18:41:00 Little doctor·

Written this time kmp The algorithm is based on next Array to move and compare pattern strings , according to nextval The comparative movement of is still under consideration , In fact, it is (wo) One (bi) sentence (jiao) generation (cai) Code thing .
Because of the time, I won't hang it out , I'll send it after I've changed it !

#include <iostream>
#include <cstdlib>
#include <vector>
#define maxsize 100
using namespace std;
		
typedef struct String{
    
	string string;
	int length;
}String;
		
int *get_next(String S,int *next)
{
    		
	int i=0;
	int j=-1;
	next[0]=-1; 
	while(i<=S.length)
	{
    	
		if(j==-1||S.string[i]==S.string[j])
		{
    
			++i;
			++j;
			next[i]=j;
			
		}
		else 
			j=next[j];
	}	
	 return next;
}		

int KMP(String Str,String S,int *next,int *nextval)
	{
    
		int i=0;
		int j=0;
		while(i<Str.length&&j<S.length)
		{
    
			
			if(j==-1||Str.string[i]==S.string[j])
			{
    
				i++;
				j++;
			}
			else
			{
    	
				j=next[j];
			}

		}
		if(j==S.length)
		 return i-S.length;
		 else 
		  return -1;
	}	
int main()
{
    	
	struct String Str;// Main string  
	struct String S;  // Pattern string  
	Str.string="aabghjvacabaababaabo";
	Str.length=20;
	S.string="abaab";
	S.length=5;
	//int *next=(int *)malloc(S.length*sizeof(int));
	int *next=new int[5];
	next=get_next(S,next);
	cout<<"next--main"<<endl; 
	for(int i=0;i<S.length;i++)
	{
    
		cout<<next[i]<<" ";
	}
	cout<<endl;
	cout<<"KMP"<<endl;
		for(int i=0;i<S.length;i++)
	{
    
		cout<<next[i]<<" ";
	}
	cout<<endl;
	int temp=KMP(Str,S,next,nextval);
	if(temp==-1)
		cout<<" Matching failure "<<endl; 
	else
	  	cout<<" The match is successful "<<endl<<" Matching position :"<<temp<<endl;
	return 0; 
}	

	

Buried pit !!!!
It took a whole week to write an algorithm for baked bun slices , What a disgrace , I am ashamed of my award !!
The algorithm is really hand-made without writing ! But I really don't have time !! Is dubious !

 This buried pit 
1. Comparison of stack area and heap area 
2. About the innocent recycling of array memory !!!( In fact, the essence is the first 
 A problem )
3. I would like to inform you , Be sure to read clearly when you write kmp in next The beginning of the array 
 The subscript is 0 still 1. It's important !!!
4. There seems to be nothing left !
 Good night, ! I wish you nb!
原网站

版权声明
本文为[Little doctor·]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/162/202206111824451583.html