java数据结构之字符串的模式匹配算法

柔情只为你懂 2022-08-23 03:59 124阅读 0赞

java中String提供了很多的字符串处理方法其中就包括子串的匹配。

今天就来介绍一下字符串中的子串的匹配算法。分为两种：一种为朴素的模式匹配算法（简称BF算法），改进的模式匹配算法（简称KMP算法）。

下面首先来介绍一下BF算法的中心思想：

这是一种带有回溯的匹配算法，简称BF算法。实现过程是从主串S的第一个字符开始和模式T的第一个字符开始比较，若相等则继续比较二者后续的的字符；否则从主串的第二个字符开始和模式T的第一个字符进行比较，重复上述过程，直至S或者T中所有的字符比较完毕。

BF算法实现（）：

package string;
    public class StringModel {
    	public int BF(char S[],char T[]){//BF字符串匹配算法
    		int i=0,j=0;
    		while(i!=(S.length-1) && j!=(T.length-1)){
    			if(S[i]==T[j]){
    				i++;
    				j++;
    			}else{
    				i=i-j+1;
    				j=0;
    			}
    		}	
    		if(j==(T.length-1)){
    			return i-j+1;
    		}else{
    			return 0;
    		}
    	}
    	public static void main(String[] args) {
    		StringModel s=new StringModel();
    		char[] S={'a','a','b','d','f','g','d','w'};
    		char[] T={'a','b','d','f'};
    		System.out.println(s.BF(S, T));
    	}
    }

最好的情况下的时间复杂度为O（m+n），最坏的情况下的时间复杂度为O（m\*n）；

KMP的算法时间复杂度为O（m+n）。具体实现留在下一篇博客中。

**如果有什么不清楚或者有啥疑问意见可以加我QQ/[微信][Link 1]  208017534  / qiang220316，欢迎一起交流一起进步。**

![Center][]

[Link 1]: http://lib.csdn.net/base/5
[Center]: /images/20220722/dd72d589089a4d75aa9f090beb2ef762.png