"前綴"和"后綴"。 "前綴"指除了最后一個字符以外，一個字符串的全部頭部組合；"后綴"指除了第一個字符以外，一個字符串的全部尾部組合。

"部分匹配"的實質(zhì)是，有時候，字符串頭部和尾部會有重復(fù)。比如，"ABCDAB"之中有兩個"AB"，那么它的"部分匹配值"就是2（"AB"的長度）。搜索詞移動的時候，第一個"AB"向后移動4位（字符串長度-部分匹配值），就可以來到第二個"AB"的位置。

KMP算法就是利用模式自身的規(guī)律來避免樸素算法的無效位移，最主要是計算模式P的前綴函數(shù)π，參考代碼如下：

package cn.ansj;public class KMP {private String text;private String pattern;KMP() { }KMP(String text, String pattern) {this.text = text;this.pattern = pattern;}public void setText(String text) {this.text = text;}public void setPattern(String pattern) {this.pattern = pattern;}public void KMPMatcher() {//匹配算法int n = text.length();int m = pattern.length();int prefix[] = computePrefix();int q = 0;int count = 0;for(int i = 0; i < n; i++) {while(q > 0 && pattern.charAt(q)!= text.charAt(i)) {q = prefix[q -1];}if(pattern.charAt(q) == text.charAt(i))q++;if(q == m) {System.out.println("Pattern occurs with shift " + ++count + "times");q = prefix[q - 1];}}if(count == 0) {System.out.println("There is no matcher!");}}private int[] computePrefix() {//前綴函數(shù)π計算int length = pattern.length();int[] prefix = new int[length];prefix[0] = 0;int k = 0;for(int i = 1; i < length; i++) {while(k > 0 && pattern.charAt(k) != pattern.charAt(i)) {k = prefix[k -1]; }if(pattern.charAt(k) == pattern.charAt(i))k++;prefix[i] = k;}return prefix;}public static void main(String[] args) {KMP kmp; if(args.length == 2) {kmp = new KMP(args[0] , args[1]);}else {kmp = new KMP();kmp.setText("ababacabacbababababacabcbabababaca");kmp.setPattern("ababaca");}kmp.KMPMatcher(); }} 執(zhí)行結(jié)果：
Pattern occurs with shift 1times Pattern occurs with shift 2times Pattern occurs with shift 3times

總結(jié)

以上是生活随笔為你收集整理的Java实现算法导论中KMP字符串匹配算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。