傳統(tǒng)的字符串模式匹配算法（也就是BF算法）就是對于主串和模式串雙雙自左向右，一個一個字符比較，如果不匹配，主串和模式串的位置指針都要回溯。這樣的算法時間復雜度為O（n＊m），其中n和m分別為串s和串t的長度。
公司主營業(yè)務(wù)：網(wǎng)站制作、成都網(wǎng)站建設(shè)、移動網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競爭能力。創(chuàng)新互聯(lián)公司是一支青春激揚、勤奮敬業(yè)、活力青春激揚、勤奮敬業(yè)、活力澎湃、和諧高效的團隊。公司秉承以“開放、自由、嚴謹、自律”為核心的企業(yè)文化，感謝他們對我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團隊有機會用頭腦與智慧不斷的給客戶帶來驚喜。創(chuàng)新互聯(lián)公司推出滎經(jīng)免費做網(wǎng)站回饋大家。
KMP 算法是由Knuth，Morris和Pratt等人共同提出的，所以成為Knuth－Morris－Pratt算法，簡稱KMP算法。KMP算法是字符串模式匹配中的經(jīng)典算法。和BF算法相比，KMP算法的不同點是匹配過程中，主串的位置指針不會回溯，這樣的結(jié)果使得算法時間復雜度只為O（n＋m）。
字符串的匹配在Java中都知道使用indexOf函數(shù)來實現(xiàn)，那么其匹配算法是怎么樣的呢？
單模式和多模式的區(qū)別就是一次遍歷主串能否將多個模式的字符串都查找出來。
英文全稱為Brute Force，暴力匹配算法，匹配字符串的方法比較暴力，也比較簡單易懂。其大概的思路就是：
我們可以看到，在極端情況下，在主串 aaaa...aab 中尋找模式串 aab ，那么總共需要尋找(n-m+1)次，且每次都需要比對m次，那么時間復雜度將是 (n-m+1)*m ，即 O(n*m) ；但實際上并不會這么低效，因為我們的使用場景中主串和模式串都不會太長，而且在每個子串和模式串進行比對時，只要中途有一個不匹配，那么當前比對就會提前結(jié)束，因此大部分情況下，時間復雜度都會比 O(n*m) 要好。
我們在BF算法的基礎(chǔ)上引入哈希算法，我們不需要將每個子串與模式串逐個字符地進行比較，而是計算得出每個子串的hash值，然后和模式串的hash值進行比較，如果有相等的，那就說明有子串和模式串匹配上了。
雖然我們只需要比對模式串和子串的hash值就能得到匹配結(jié)果，次數(shù)為(n-m+1)，但是對每個子串進行hash計算的時候，是要遍歷每個字符的，因此次數(shù)也是m，那么總的時間復雜度還是 O(n*m) ，并沒有明顯地提升。
那么我們該如何想出一個辦法，使得每個子串hash值的計算時間得到提升呢？這就是RK算法的精髓，假設(shè)子串包含的字符集中元素個數(shù)為k，那么就用k進制數(shù)來代表這個子串，然后hash的過程就是將這個k進制的數(shù)轉(zhuǎn)換為十進制的數(shù)，這個十進制的數(shù)就是該子串的hash值。
相鄰子串的hash值計算是有規(guī)律的，我們只需要遍歷一次主串就能得到所有子串的hash值，算法復雜度為O(n)，而不是像原先一樣，每個子串都需要O(m)的時間復雜度。
然后將模式串的hash值和所有子串的hash值進行比較，每次比較的時間復雜度是 O(1) ，總共比較(n-m+1)次，所以RK算法的總的時間開銷為 O(n)+O(1)*O(n-m+1) ，即為 O(n) ，時間復雜度比BF算法更加高效。
當然，有hash的地方就有可能會存在hash沖突，有可能子串和hash值和模式串的hash值是一樣的，但內(nèi)容就是不一樣，此時怎么辦呢？其實很簡單，對于hash值一樣的子串，我們增加雙保險，再比較一下這m個字符是否都一樣即可，總的時間開銷為 O(n)+O(1)*O(n-m+1)+O(m) ，即為 O(n) 。
如果極端情況下出現(xiàn)了很多hash沖突呢？我們對于每個和模式串相同hash值的子串都需要逐一再進行比較，那么總的時間開銷就會為 O(n)+O(1)*O(n-m+1)+O(m)*O(n-m+1) ，即為 O(n*m) ，不過這種概率太小了，大部分情況下都不會這樣。
在真正的文本編輯器中查找和替換某個字符串時，使用的算法既不是上述的BF算法，也不是RK算法；BF算法只適合不是很長的主串，RK算法則要設(shè)計一個沖突概率很低的hash算法，這個比較困難，所以實際使用的是BM算法，它是工程中非常常用的一種字符串匹配算法，效率也是最高的。
算法的思想和過程有些復雜，待以后整理。
KMP算法在本質(zhì)上是和BM算法一樣的。算法的思想和過程有些復雜，待以后整理。
瀏覽器輸入框中的智能輸入匹配是怎么實現(xiàn)的，它是怎么做動態(tài)字符串匹配查找的呢？這就用到了Trie樹。
又名字典樹，是一種專門用來快速查找字符串前綴匹配結(jié)果的樹形結(jié)構(gòu)，其本質(zhì)就是將所有字符串的重復的前綴合并在一起，構(gòu)造一個多叉樹。
其中，根節(jié)點不包含任何信息，每個節(jié)點表示一個字符，從根節(jié)點到紅色節(jié)點的一條路徑表示存儲的一個字符串。當我們在如上Trie樹中查找"he"時，發(fā)現(xiàn)"he"并非是一個字符串，而是"hello"和"her"的公共前綴，那么就會找到這兩個字符串返回。
Trie樹在內(nèi)存中是如何存儲的呢？因為每一個節(jié)點都可能是包含所有字符的，所以每一個節(jié)點都是一個數(shù)組（或者散列表），用來存儲每個字符及其后綴節(jié)點的指針。
使用Trie樹，最開始構(gòu)建的時候，時間復雜度為 O(n) ，其中n為所有字符串長度之和，但是一旦構(gòu)建完成，頻繁地查詢某個字符串是非常高效的，時間復雜度為 O(k) ，其中k為查找字符串的長度。
Trie樹雖然查詢效率很高，但是比較浪費內(nèi)存，每一個節(jié)點都必須維護一個數(shù)組存放所有可能的字符數(shù)據(jù)及其指向下一個節(jié)點的指針，因此在所有字符串公共前綴并不多的時候，內(nèi)存空間浪費地就更多了。這種問題其實也有對應(yīng)的解決辦法，我們可以不使用數(shù)組，而是使用有序數(shù)組、散列表、紅黑樹來存放，可以相應(yīng)地降低性能來節(jié)省內(nèi)存空間。
Trie樹除了可以實現(xiàn)瀏覽器動態(tài)輸入內(nèi)容查找候選項的功能外，還可以實現(xiàn)多模式地敏感詞匹配功能。假設(shè)我們需要對用戶輸入的內(nèi)容進行敏感詞檢查，將所有的敏感內(nèi)容用***代替，那么該如何實現(xiàn)呢？
首先我們可以維護一個敏感詞字典，使用上述四種單模式匹配算法也可以實現(xiàn)，但是需要遍歷N次用戶輸入的內(nèi)容，其中N是所有敏感詞的模式串，顯得非常低效。但是我們?nèi)绻麑⒚舾性~字典維護為一個Trie樹，然后將用戶輸入的內(nèi)容從位置0開始在Trie樹中進行查詢，如果匹配到紅色節(jié)點，那么說明有敏感詞；如果沒有匹配到紅色節(jié)點，就從用戶輸入內(nèi)容的下一個位置開始繼續(xù)在Trie樹中查詢，直至將用戶輸入內(nèi)容遍歷完，因此我們只是遍歷了一遍主串。
然而更高效的多模式字符串匹配使用地更多的是如下的AC自動機。
如果把Trie樹比作BF算法，KMP算法是BF算法的改進，那么AC自動機就是利用同樣的思想改進了Trie樹。
算法的思想和過程有些復雜，待以后整理。
在編寫程序猿的時候，你需要仔細的去對照每一個字，因為如果出現(xiàn)一個字錯誤的話，那么就會導致編程不成功。
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
public class WordsCount {
public static void main(String args[]) throws IOException{
final String source = "source.txt";
final String target = "sentive.txt";
final String[] WORDS = getDictFromFile(target);
final int[] countAry = new int[WORDS.length];
BufferedReader bf = new BufferedReader(new FileReader(source));
StringBuilder sb = new StringBuilder();
String content = null;
while((content = bf.readLine()) != null){
sb.append(content);
}
String str = sb.toString();
for(int i = 0; i WORDS.length; i++){
countAry[i] = (str.length() - str.replaceAll(WORDS[i], "").length()) / WORDS[i].length();
System.out.println(WORDS[i] + "\t" + countAry[i]);
}
bf.close();
}
private static String[] getDictFromFile(String target) throws IOException {
BufferedReader bf = new BufferedReader(new FileReader(target));
List list = new ArrayList();
String word = null;
while((word = bf.readLine()) != null){
list.add(word.trim());
}
String[] words = new String[list.size()];
for(int i = 0; i list.size(); i++){
words[i] = (String) list.get(i);
}
return words;
}
}
----------------文件名保存為WordsCount.java
javac WordsCount.java
java WordsCount.class
嚴格注意大小寫，
用你的兩個文件內(nèi)容測試結(jié)果
hello 1
java 1
sb 2
Java的String的indexOf方法性能最好，其次是KMP算法，其次是傳統(tǒng)的BF算法，當然，對比有點牽強，SUN的算法也使用Java來實現(xiàn)、用的看著不像是KMP，還需要詳細研究一下。
測試代碼如下所示：
package com.test.test.kmp;
import java.util.Random;
public class KMPTest {
public static void main(String[] args) {
test();
}
//
public static void test() {
//
int allLen = 8000000;
int subLen = 11;
int charLen = 4;
String cl = buildString(charLen);
int times = 50;
//
testMatch(allLen, subLen, cl, times);
}
重慶分公司
重慶分公司
