Java数据结构--串的模式匹配算法

墨蓝 2023-10-06 09:51 58阅读 0赞

## `一、Brute-Force模式匹配算法` ##

public class BruteForce {
        
    	
    	/**
    	 * Brute-Force（暴风算法）
    	 * 算法思想：
    	 * 		从目标串s的第一个字符起和模式串t的第一个字符进行比较，若相等，则继续逐个比较后续字符，
    	 * 否则从s串的第二个字符起再重新和串t进行比较。以此类推，直至串t中每个字符依次和串s的一
    	 * 个连续的字符序列相等，则称为模式匹配成功，此时串t的第一个字符在串s中的位置就是t在s中
    	 * 的位置，否则模式匹配不成功
    	 * 
    	 * 这种匹配模式的主串指针需要回溯，速度慢
    	 * 
    	 * 时间复杂度：
    	 * 		最好情况：只需要一次，即比较子串的长度的次数为n=O(n)
    	 * 		最差情况：每次比较时都发现字串的最后一个字符串和主串不相等，故需要比较(m - n) * n + n = (m - n + 1) * n = O(m * n)次
    	 * 		一般情况：O(m + n);从最好到最坏情况统计总的比较次数，然后取平均值
    	 * 
    	 * @param s 主串
    	 * @param t 子串
    	 * @param pos 为从哪个位置开始匹配
    	 * @return
    	 */
    	public static int bf(SeqString s, SeqString t, int pos) {
        
    		/* 非法操作  */
    		if (pos < 0 || t.curlen < 0 ) {
        
    			return 0;
    		}
    		int i = pos, j = 0;
    		while(i < s.curlen && j <t.curlen) {
          
    			if(s.data[i] == t.data[j]) {
         // 相等
    				i++;
    				j++;
    			} else {
        
    				i = i - j + 1;
    				j = 0;
    			}
    		}
    		if (j >= t.curlen) {
        
    			return i - t.curlen; // 或者i - j + 1
    		} else {
        
    			return 0; // 没找到
    		}
    	}
    	
    }

## `二、KMP模式匹配算法` ##

public class Kmp {
        
    	
    	
    	public static void main(String[] args) {
        
    		System.out.println(Kmp.kmp("bacbababadababacambabacaddababacasdsd", "ababaca", Kmp.next("ababaca")));
    	}
    
    	/**
    	 * KMP
    	 * 
    	 */
    	public static int kmp(String str, String sub, int[] next) {
        
    		char[] parent = str.toCharArray(); // 主串
    		char[] children = sub.toCharArray(); // 模式串
    		
    		int k = -1; // 模式串在主串中的位置，默认-1不存在
    		
    		for (int i = 0; i < parent.length; i++) {
        
    			
    			// children和parent不匹配，且k>-1（表示children和parent有部分匹配）
    			while (k > -1 && children[k+1] != parent[i]) {
        
    				k = next[k]; //往前回溯
    			}
    			
    			if (children[k+1] == parent[i]) {
         
    				k = k + 1;
    			}
    			
    			if (k == children.length - 1) {
         //说明k移动到children的最末端
    				return i - children.length + 1;
    			}
    		}
    		return -1;
    	}
    	
    	/**
    	 * 偏移函数
    	 * 
    	 * a  ab 	aba 	abab 	ababa 	ababac 			ababaca
    	 * a    ab    aba	  abab	  ababa       ababac	      ababaca
    	 * 
    	 * @param sub
    	 * @return
    	 */
    	public static int[] next(String sub) {
        
    		int[] next = new int[sub.length()]; 
    		next[0] = -1;	// 第一个一定没有最优前缀和最优后缀相等
    		char[] str = sub.toCharArray();
    		int i = 1; // 后缀标识
    		int k = -1; //前缀标识(也是最优前后缀相同部分的长度)
    		
    		for (i = 1; i < sub.length(); i++) {
        
    			while (k > -1 && str[k+1] != str[i]) {
        
    				k = next[k];
    			}
    			if (str[k+1] == str[i]) {
        
    				k = k + 1;
    			}
    			next[i] = k; // 计算出来的最优前后缀相同部分的长度
    		}
    		return next;
    	}
    	
    }
    ```