【数据结构】串的应用：模式匹配暴力算法BF

Dear 丶 2023-09-23 19:16 57阅读 0赞

### 串的应用–模式匹配 ###

暴力算法–BF：

int patternMatchingBF(struct String *main,struct String *sub) {
        
    	int i = 0, j = 0,k = 0;
    	while (i<main->length && j<sub->length) {
        
    		if (main->string[i] == sub->string[j]) {
        
    			i++;
    			j++;
    		}
    		else {
        
    			k++;
    			j = 0;
    			i = k;
    		}
    	}
    	if (j == sub->length) {
        
    		return k;
    	}
    	else{
        
    		return -1;
    	}
    }
    int loc = patternMatchingBF(s,t);
    	if (loc!=-1) {
        
    		printf("匹配成功，初始下标在:%d",loc);
    	}
    	else {
        
    		printf("匹配失败");
    	}

思路：  
定义3个变量 i,j,k

> i指向的是主串中的元素，j指向的是子串中的元素，k指向的是主串中作比较的子串的初始位置的值

*  每次比较成功会对 i++ , j++ ,使其指向下一个元素，继续进行比较，直到匹配成功为止。
 *  比较失败时，会重置j的值，即重新比较，然而i的值会回溯到k的下一个位置，即主串中当前比较的子串初始位置的下一个位置。

![请添加图片描述][20fd2a09884b4cf2aa3b53da6f0b08a4.png]  
![请添加图片描述][2faea419ba874a21b69d783aeebcebef.png]  
![请添加图片描述][5e73a7a881ba40ba87638f8e3d2ae55f.png]

[20fd2a09884b4cf2aa3b53da6f0b08a4.png]: https://img-blog.csdnimg.cn/20fd2a09884b4cf2aa3b53da6f0b08a4.png
[2faea419ba874a21b69d783aeebcebef.png]: https://img-blog.csdnimg.cn/2faea419ba874a21b69d783aeebcebef.png
[5e73a7a881ba40ba87638f8e3d2ae55f.png]: https://img-blog.csdnimg.cn/5e73a7a881ba40ba87638f8e3d2ae55f.png