建站
咨詢
售后
建站咨詢
新聞中心
Java編程實(shí)現(xiàn)字符串的模式匹配
傳統(tǒng)的字符串模式匹配算法（也就是BF算法）就是對(duì)于主串和模式串雙雙自左向右，一個(gè)一個(gè)字符比較，如果不匹配，主串和模式串的位置指針都要回溯。這樣的算法時(shí)間復(fù)雜度為O（n＊m），其中n和m分別為串s和串t的長(zhǎng)度。
公司主營(yíng)業(yè)務(wù)：網(wǎng)站制作、成都網(wǎng)站建設(shè)、移動(dòng)網(wǎng)站開(kāi)發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競(jìng)爭(zhēng)能力。創(chuàng)新互聯(lián)公司是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開(kāi)放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對(duì)我們的高要求，感謝他們從不同領(lǐng)域給我們帶來(lái)的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶帶來(lái)驚喜。創(chuàng)新互聯(lián)公司推出滎經(jīng)免費(fèi)做網(wǎng)站回饋大家。
KMP 算法是由Knuth，Morris和Pratt等人共同提出的，所以成為Knuth－Morris－Pratt算法，簡(jiǎn)稱KMP算法。KMP算法是字符串模式匹配中的經(jīng)典算法。和BF算法相比，KMP算法的不同點(diǎn)是匹配過(guò)程中，主串的位置指針不會(huì)回溯，這樣的結(jié)果使得算法時(shí)間復(fù)雜度只為O（n＋m）。
字符串匹配算法的使用（未完待整理）
字符串的匹配在Java中都知道使用indexOf函數(shù)來(lái)實(shí)現(xiàn)，那么其匹配算法是怎么樣的呢？
單模式和多模式的區(qū)別就是一次遍歷主串能否將多個(gè)模式的字符串都查找出來(lái)。
英文全稱為Brute Force，暴力匹配算法，匹配字符串的方法比較暴力，也比較簡(jiǎn)單易懂。其大概的思路就是：
我們可以看到，在極端情況下，在主串 aaaa...aab 中尋找模式串 aab ，那么總共需要尋找(n-m+1)次，且每次都需要比對(duì)m次，那么時(shí)間復(fù)雜度將是 (n-m+1)*m ，即 O(n*m) ；但實(shí)際上并不會(huì)這么低效，因?yàn)槲覀兊氖褂脠?chǎng)景中主串和模式串都不會(huì)太長(zhǎng)，而且在每個(gè)子串和模式串進(jìn)行比對(duì)時(shí)，只要中途有一個(gè)不匹配，那么當(dāng)前比對(duì)就會(huì)提前結(jié)束，因此大部分情況下，時(shí)間復(fù)雜度都會(huì)比 O(n*m) 要好。
我們?cè)贐F算法的基礎(chǔ)上引入哈希算法，我們不需要將每個(gè)子串與模式串逐個(gè)字符地進(jìn)行比較，而是計(jì)算得出每個(gè)子串的hash值，然后和模式串的hash值進(jìn)行比較，如果有相等的，那就說(shuō)明有子串和模式串匹配上了。
雖然我們只需要比對(duì)模式串和子串的hash值就能得到匹配結(jié)果，次數(shù)為(n-m+1)，但是對(duì)每個(gè)子串進(jìn)行hash計(jì)算的時(shí)候，是要遍歷每個(gè)字符的，因此次數(shù)也是m，那么總的時(shí)間復(fù)雜度還是 O(n*m) ，并沒(méi)有明顯地提升。
那么我們?cè)撊绾蜗氤鲆粋€(gè)辦法，使得每個(gè)子串hash值的計(jì)算時(shí)間得到提升呢？這就是RK算法的精髓，假設(shè)子串包含的字符集中元素個(gè)數(shù)為k，那么就用k進(jìn)制數(shù)來(lái)代表這個(gè)子串，然后hash的過(guò)程就是將這個(gè)k進(jìn)制的數(shù)轉(zhuǎn)換為十進(jìn)制的數(shù)，這個(gè)十進(jìn)制的數(shù)就是該子串的hash值。
相鄰子串的hash值計(jì)算是有規(guī)律的，我們只需要遍歷一次主串就能得到所有子串的hash值，算法復(fù)雜度為O(n)，而不是像原先一樣，每個(gè)子串都需要O(m)的時(shí)間復(fù)雜度。
然后將模式串的hash值和所有子串的hash值進(jìn)行比較，每次比較的時(shí)間復(fù)雜度是 O(1) ，總共比較(n-m+1)次，所以RK算法的總的時(shí)間開(kāi)銷為 O(n)+O(1)*O(n-m+1) ，即為 O(n) ，時(shí)間復(fù)雜度比BF算法更加高效。
當(dāng)然，有hash的地方就有可能會(huì)存在hash沖突，有可能子串和hash值和模式串的hash值是一樣的，但內(nèi)容就是不一樣，此時(shí)怎么辦呢？其實(shí)很簡(jiǎn)單，對(duì)于hash值一樣的子串，我們?cè)黾与p保險(xiǎn)，再比較一下這m個(gè)字符是否都一樣即可，總的時(shí)間開(kāi)銷為 O(n)+O(1)*O(n-m+1)+O(m) ，即為 O(n) 。
如果極端情況下出現(xiàn)了很多hash沖突呢？我們對(duì)于每個(gè)和模式串相同hash值的子串都需要逐一再進(jìn)行比較，那么總的時(shí)間開(kāi)銷就會(huì)為 O(n)+O(1)*O(n-m+1)+O(m)*O(n-m+1) ，即為 O(n*m) ，不過(guò)這種概率太小了，大部分情況下都不會(huì)這樣。
在真正的文本編輯器中查找和替換某個(gè)字符串時(shí)，使用的算法既不是上述的BF算法，也不是RK算法；BF算法只適合不是很長(zhǎng)的主串，RK算法則要設(shè)計(jì)一個(gè)沖突概率很低的hash算法，這個(gè)比較困難，所以實(shí)際使用的是BM算法，它是工程中非常常用的一種字符串匹配算法，效率也是最高的。
算法的思想和過(guò)程有些復(fù)雜，待以后整理。
KMP算法在本質(zhì)上是和BM算法一樣的。算法的思想和過(guò)程有些復(fù)雜，待以后整理。
瀏覽器輸入框中的智能輸入匹配是怎么實(shí)現(xiàn)的，它是怎么做動(dòng)態(tài)字符串匹配查找的呢？這就用到了Trie樹(shù)。
又名字典樹(shù)，是一種專門用來(lái)快速查找字符串前綴匹配結(jié)果的樹(shù)形結(jié)構(gòu)，其本質(zhì)就是將所有字符串的重復(fù)的前綴合并在一起，構(gòu)造一個(gè)多叉樹(shù)。
其中，根節(jié)點(diǎn)不包含任何信息，每個(gè)節(jié)點(diǎn)表示一個(gè)字符，從根節(jié)點(diǎn)到紅色節(jié)點(diǎn)的一條路徑表示存儲(chǔ)的一個(gè)字符串。當(dāng)我們?cè)谌缟蟃rie樹(shù)中查找"he"時(shí)，發(fā)現(xiàn)"he"并非是一個(gè)字符串，而是"hello"和"her"的公共前綴，那么就會(huì)找到這兩個(gè)字符串返回。
Trie樹(shù)在內(nèi)存中是如何存儲(chǔ)的呢？因?yàn)槊恳粋€(gè)節(jié)點(diǎn)都可能是包含所有字符的，所以每一個(gè)節(jié)點(diǎn)都是一個(gè)數(shù)組（或者散列表），用來(lái)存儲(chǔ)每個(gè)字符及其后綴節(jié)點(diǎn)的指針。
使用Trie樹(shù)，最開(kāi)始構(gòu)建的時(shí)候，時(shí)間復(fù)雜度為 O(n) ，其中n為所有字符串長(zhǎng)度之和，但是一旦構(gòu)建完成，頻繁地查詢某個(gè)字符串是非常高效的，時(shí)間復(fù)雜度為 O(k) ，其中k為查找字符串的長(zhǎng)度。
Trie樹(shù)雖然查詢效率很高，但是比較浪費(fèi)內(nèi)存，每一個(gè)節(jié)點(diǎn)都必須維護(hù)一個(gè)數(shù)組存放所有可能的字符數(shù)據(jù)及其指向下一個(gè)節(jié)點(diǎn)的指針，因此在所有字符串公共前綴并不多的時(shí)候，內(nèi)存空間浪費(fèi)地就更多了。這種問(wèn)題其實(shí)也有對(duì)應(yīng)的解決辦法，我們可以不使用數(shù)組，而是使用有序數(shù)組、散列表、紅黑樹(shù)來(lái)存放，可以相應(yīng)地降低性能來(lái)節(jié)省內(nèi)存空間。
Trie樹(shù)除了可以實(shí)現(xiàn)瀏覽器動(dòng)態(tài)輸入內(nèi)容查找候選項(xiàng)的功能外，還可以實(shí)現(xiàn)多模式地敏感詞匹配功能。假設(shè)我們需要對(duì)用戶輸入的內(nèi)容進(jìn)行敏感詞檢查，將所有的敏感內(nèi)容用***代替，那么該如何實(shí)現(xiàn)呢？
首先我們可以維護(hù)一個(gè)敏感詞字典，使用上述四種單模式匹配算法也可以實(shí)現(xiàn)，但是需要遍歷N次用戶輸入的內(nèi)容，其中N是所有敏感詞的模式串，顯得非常低效。但是我們?nèi)绻麑⒚舾性~字典維護(hù)為一個(gè)Trie樹(shù)，然后將用戶輸入的內(nèi)容從位置0開(kāi)始在Trie樹(shù)中進(jìn)行查詢，如果匹配到紅色節(jié)點(diǎn)，那么說(shuō)明有敏感詞；如果沒(méi)有匹配到紅色節(jié)點(diǎn)，就從用戶輸入內(nèi)容的下一個(gè)位置開(kāi)始繼續(xù)在Trie樹(shù)中查詢，直至將用戶輸入內(nèi)容遍歷完，因此我們只是遍歷了一遍主串。
然而更高效的多模式字符串匹配使用地更多的是如下的AC自動(dòng)機(jī)。
如果把Trie樹(shù)比作BF算法，KMP算法是BF算法的改進(jìn)，那么AC自動(dòng)機(jī)就是利用同樣的思想改進(jìn)了Trie樹(shù)。
算法的思想和過(guò)程有些復(fù)雜，待以后整理。
求一個(gè)串中出現(xiàn)的第一個(gè)最長(zhǎng)重復(fù)子串？
在編寫程序猿的時(shí)候，你需要仔細(xì)的去對(duì)照每一個(gè)字，因?yàn)槿绻霈F(xiàn)一個(gè)字錯(cuò)誤的話，那么就會(huì)導(dǎo)致編程不成功。
JAVA詞頻統(tǒng)計(jì) 算法解釋&如何編譯 代碼用貼
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
嚴(yán)格注意大小寫，
用你的兩個(gè)文件內(nèi)容測(cè)試結(jié)果
hello 1
java 1
sb 2
StringBuilder有多消耗性能
Java的String的indexOf方法性能最好，其次是KMP算法，其次是傳統(tǒng)的BF算法，當(dāng)然，對(duì)比有點(diǎn)牽強(qiáng)，SUN的算法也使用Java來(lái)實(shí)現(xiàn)、用的看著不像是KMP，還需要詳細(xì)研究一下。
測(cè)試代碼如下所示：
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);
}
名稱欄目：bf算法代碼java,bf算法完整代碼
分享鏈接：http://www.dlmjj.cn/article/dsiegho.html
