【数据结构与算法】字符串匹配KMP算法

快来打我* 2022-08-11 19:59 183阅读 0赞

首先需要了解一下BF暴力匹配算法，这个算法为每一个串设置一个指针，然后两个指针同时后移，出现不匹配的情况后，主串指针回到开始后移之前的位置的下一位，模式串指针回到最开始。

对比一下KMP算法，同样是设置两个指针，然后两个指针同时后移，出现不匹配的情况后，主串指针不变，模式串指针回溯一定的距离。具体模式串指针回溯多少，是第一次看KMP算法的人比较难以理解的，其实仔细想想，模式串的前缀和后缀其实也是在做匹配，当P\[K\]!=P\[J\]时就是失配，那么前缀的指针就需要回溯，所以后k=next\[k\]。

*  代码实现

/**
     * 源码名称：KMP.java 
     * 日期：2014-09-03 
     * 程序功能：KMP算法 
     * 版权：CopyRight@A2BGeek 
     * 作者：A2BGeek
     */
    public class KMP {
    	public int[] getNext(String in) {
    		int[] next = new int[in.length()];
    		int j = 0;
    		int k = -1;
    		next[j] = k;
    		while (j < next.length - 1) {
    			if (k == -1 || in.charAt(k) == in.charAt(j)) {
    				j++;
    				k++;
    				next[j] = k;
    			} else {
    				k = next[k];
    			}
    		}
    		for(int i : next) {
    			System.out.print(i + " ");
    		}
    		System.out.println();
    		return next;
    	}
    
    	public int kmp(String s, String p) {
    		int i = 0;
    		int j = 0;
    		int[] next = getNext(p);
    		while (i < s.length() && j < p.length()) {
    			if (j == -1 || s.charAt(i) == p.charAt(j)) {
    				i++;
    				j++;
    			} else {
    				j = next[j];
    			}
    		}
    		if (j == p.length()) {
    			return 1;
    		} else {
    			return -1;
    		}
    	}
    
    	public static void main(String[] args) {
    		KMP kmp = new KMP();
    		String s = "acbfdfjkdhg";
    		String p = "dfdj";
    		System.out.println(kmp.kmp(s, p));
    	}
    }