preface

String matching algorithm is also a very classic algorithm, often encountered in the interview, and BF algorithm is a simple algorithm in string pattern matching

1. What is BF algorithm

BF algorithm, also known as Brute Force algorithm, is a common pattern matching algorithm with simple idea and simple code structure

The idea of BF algorithm is to match the first character of the target string S with the first character of the pattern string T. If they are equal, the second character of S and the second character of T will be compared. If not, the second character of S is compared with the first character of T, and so on, until the final match is obtained.

2. Code implementation

Analysis:

To complete the matching work for all the characters, we can traverse the parent string and compare with the sub-string one by one. If they are the same, the string matching bit will move later. If they are not successful, the string matching bit will return to zero

Code:

void Get(string a,string b)
{
    int i,j=0;
    for(i=0; i<a.length(a); i++) {if(a[i]==b[j])  // If the match is successful, the string matches the character one bit later
        	j++;  
        else        // If not, the string starts again from the first, and the parent string backtracks
       	{
       		i=i-j+1;
       		j=0;
       	}	        
        if(j==b.length())   
        {
            cout<<"Yes Ok";
            return; }}if(j! =b.length()) cout<<"Sorry"
}
Copy the code

3. Complexity of the algorithm

If the parent string length bit is m and the string length bit is n, then:

Worst-case Avg. Time complexity bit: O(m+ N) Worst-case Avg. Time complexity bit: O(m*n)