KMP算法（java）

以你之姓@ 2022-06-07 08:22 144阅读 0赞

KMP算法是在字符串M中查找是否包含字符串N，存在返回字符串M匹配的字符首位置，将复杂度O(mn)降为O(m+n)

要看对KMP算法的理解，请参考[字符串匹配的KMP算法][KMP]

要看其中对匹配表的理解，请参考[ KMP算法最浅显理解——一看就明白 ][KMP 1]

下面是基于算法整理的Java代码：

public class KMP {
    
    	private static int[] getNext(String b) {
    		int len = b.length();
    		int j = 0;
    
    		int next[] = new int[len + 1];
    		next[0] = next[1] = 0;
    
    		for (int i = 1; i < len; i++) {
    			while (j > 0 && b.charAt(i) != b.charAt(j)) {
    				j = next[j];
    			}
    			if (b.charAt(i) == b.charAt(j)) {
    				j++;
    			}
    			next[i + 1] = j;
    		}
    
    		return next;
    	}
    
    	public static List<Integer> search(String original, String find) {
    		List<Integer> pos = new ArrayList<Integer>();
    
    		int[] next = getNext(find);
    
    		int j = 0;
    		for (int i = 0; i < original.length(); i++) {
    			while (j > 0 && original.charAt(i) != find.charAt(j))
    				j = next[j];
    			if (original.charAt(i) == find.charAt(j)) {
    				j++;
    			}
    				
    			if (j == find.length()) {
    				pos.add(i - j + 1);
    				j = 0;
    			}
    		}
    
    		return pos;
    	}
    	
    	public static int searchFirst(String original, String find) {
    		int pos = -1;
    
    		int[] next = getNext(find);
    
    		int j = 0;
    		for (int i = 0; i < original.length(); i++) {
    			while (j > 0 && original.charAt(i) != find.charAt(j))
    				j = next[j];
    			if (original.charAt(i) == find.charAt(j)) {
    				j++;
    			}
    				
    			if (j == find.length()) {
    				pos = i - j + 1;
    				break;
    			}
    		}
    
    		return pos;
    	}
    	
    	public static void main(String[] args) {
    	    String a = "abcaabababaa";
    	    String b = "abaa";
    	    
    	    //List<Integer> aaa = search(a, b);
    	    int bbb = searchFirst(a, b);
    	    
    	    //System.out.println(aaa);
    	    System.out.println(bbb);
        }
    }

[KMP]: http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
[KMP 1]: http://blog.csdn.net/starstar1992/article/details/54913261