Java实现字符串匹配的BF算法和KMP算法

爱被打了一巴掌 2023-07-11 06:08 7阅读 0赞

[*点击进入尚硅谷数据结构和算法Java代码导航*][Java]

## 1，BF算法 ##

字符串匹配的暴力搜索算法 Brute Force。

## 2，KMP算法 ##

算法原理和next数组的实现参照视频https://www.bilibili.com/video/av3246487

public class StringMatch {
        
    
    	/**
    	 * 字符串匹配的暴力搜索算法  Brute Force
    	 * @param s1 主串
    	 * @param s2 字串
    	 * @return 返回匹配的位置，没有返回-1
    	 */
    	public static int BF(String s1, String s2) {
        
    		int k = -1;
    		char[] c1 =s1.toCharArray(); 
    		char[] c2 =s2.toCharArray(); 
    		for(int i=0; i<c1.length - c2.length + 1; i++) {
        
    			int j = 0;
    			int n = i;
    			while(j<c2.length && c1[n] == c2[j]) {
        //顺序不能反
    				n++;
    				j++;
    			}
    			if(j == c2.length) {
        
    				k = i;
    			}
    		}
    		return k;
    	}
    	//构建next数组
    	public static int[] makeNext(char[] c) {
        
    		int[] next = new int[c.length];//next数组初始化后默认值为0,正好我们需要将数组初始化为0
    		for(int i=1,j=0; i<c.length; i++) {
        
    			if(c[j] == c[i]) {
        
    				next[i] = j + 1;
    				j++;
    			}else {
        
    				while(j != 0) {
        //当j不为零的时候，移动j的位置，直到匹配上或者j等于0
    					j = next[j-1];
    					if(c[i] == c[j]) {
        
    						next[i] = j + 1;
    						break;
    					}
    				}//当j=0还匹配不上的话，说明没有共同前后缀，令next[i]=0,由于数组初始化为0这里不写
    			}
    		}
    		return next;
    	}
    	/**
    	 * 
    	 * @param s1 主串
    	 * @param s2 子串
    	 * @return 返回匹配到的位置
    	 */
    	public static int KMP(String s1, String s2) {
        
    		int k = -1;
    		char[] c1 =s1.toCharArray(); 
    		char[] c2 =s2.toCharArray();
    		int[] next = makeNext(c2);
    		int i=0,j=0;
    		while(i<c1.length) {
        
    			if(c1[i] == c2[j]) {
        //匹配到时i和j同时右移
    				i++;
    				j++;
    			}else {
        //如果没匹配到，分情况讨论
    				if(j == 0) {
        //j等于0，在子串的起始位置，此时i右移
    					i++;
    				}else {
        //j不等于0，移动子串
    					j = next[j-1];
    				}
    			}
    			if(j == c2.length) {
        
    				return i-j;
    			}
    		}
    		return k;
    	}
    	
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
     
    		String s1 = "abxabcabcaby";
    		String s2 = "abcaby";
    		System.out.println(KMP(s1, s2));
    	}
    }

[Java]: https://blog.csdn.net/weixin_44963741/article/details/105228982