String matching: find a substring in a string

demand

Our usual software development , Especially embedded development , String matching is a very important algorithm . At present, there are many commonly used string matching algorithms , Here are some .

Concrete algorithm

Conventional methods

The string is stored in the fixed length sequential storage structure of the character array , You can use the count pointer to indicate the character position currently being compared between the main string and the mode string . The basic idea of the algorithm is ： From the... Of the main string i The first character of the pattern string is compared with the first character of the pattern string . If equal , Then continue to compare the following characters ; Otherwise, the next character of the main string will be compared with the first character of the mode string . Know that the pattern string is compared , Represents that there is a pattern string in the main string .

Program

int index(string S,stringT,int pos)
{
    
    int i,j;
    i=pos;
    j=1;
    while(i<=S[0]&&j<=T[0])
    {
    
        if(S[i]==T[j])
        {
    
            ++i;
            j++;
        }
        else
        {
    
            i=i-j+2;
            j=1;
        }
    }
    if(j>T[0])
    return i-T[0];
    else return 0;

}

KMP Algorithm

KMP The algorithm is also called Knut — Maurice — Pratt operation , Is a very efficient string matching algorithm .KMP Algorithm is an improved string matching algorithm , The key is to use the information after matching failure , Reduce the matching times between pattern string and main string as much as possible to achieve the purpose of fast matching . This algorithm can be used in O（n+m） Complete the string pattern matching operation on the order of time . The idea of the algorithm is ： Whenever there are different characters in the matching process , No backtracking pointer is required , It's about taking advantage of what you've got “ Partial matching ” The result is to turn the pattern to the right “ rolling ” After a distance as far as possible , Continue to compare .

First of all, we need to define a concept , The longest string before - suffix .
give an example , character string abcdab
A collection of prefixes ：{a,ab,abc,abcd,abcda}
A collection of suffixes ：{b,ab,dab,cdab,bcdab}
So the longest time ago - The suffix is ab.

and KMP The algorithm will be the longest before - The suffix concept is used in next Array .
next The meaning of the array values ： Represents the string before the current character , What is the length of the same Prefix suffix . For example, if next [j] = k, representative j The length of the string before is the largest k The same Prefix suffix of .
This means that when a character mismatch , This character corresponds to next The value will tell you that the next matching step is , Where should the pattern string jump to （ Jump to the next [j] The location of ）. If next [j] be equal to 0 or -1, Jump to the beginning of the pattern string , if next [j] = k And k > 0, Represents that the next match jumps to j A character before , Instead of jumping to the beginning , And specifically skip k Characters .

Program

First we need to ask next Array

typedef struct
{
    	
	char data[MaxSize];
	int length;			// String length 
} SqString;
void GetNext(SqString t,int next[])		// By mode string t Find out next value 
{
    
	int i,k;
	i=0;k=-1;
	next[0]=-1;// There is no string before the first character , Given value -1
	while (i<t.length-1) 
	{
    	
		if (k==-1 || t.data[i]==t.data[k]) 	//k by -1 When the characters are equal 
		{
    	
			i++;k++;
			next[i]=k;
       	}
       	else
		{
    
			k=next[k];
		}
	}
}

KPM Algorithm

int KMPIndex(SqString s,SqString t)  
{
    

	int next[MaxSize],i=0,j=0;
	GetNext(t,next);
	while (i<s.length && j<t.length) 
	{
    
		if (j==-1 || s.data[i]==t.data[j]) 
		{
    
			i++;j++;  			//i,j Each increase 1
		}
		else j=next[j]; 		
    }
    if (j>=t.length)
		return(i-t.length);  	// Returns the first character subscript of the matching pattern string 
    else  
		return(-1);        		// Returns the mismatch flag 
}

follow-up

If you want to learn more about the Internet of things 、 Smart home project knowledge , Can pay attention to my Program design column .
After subscribing to the column , I can talk to you on WeChat official account .

It's not easy to write , Thank you for your support .