Java編程實(shí)現(xiàn)字符串的模式匹配

傳統(tǒng)的字符串模式匹配算法（也就是BF算法）就是對于主串和模式串雙雙自左向右，一個(gè)一個(gè)字符比較，如果不匹配，主串和模式串的位置指針都要回溯。這樣的算法時(shí)間復(fù)雜度為O（n＊m），其中n和m分別為串s和串t的長度。

公司主營業(yè)務(wù)：網(wǎng)站制作、成都網(wǎng)站建設(shè)、移動(dòng)網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競爭能力。創(chuàng)新互聯(lián)公司是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶帶來驚喜。創(chuàng)新互聯(lián)公司推出滎經(jīng)免費(fèi)做網(wǎng)站回饋大家。

KMP 算法是由Knuth，Morris和Pratt等人共同提出的，所以成為Knuth－Morris－Pratt算法，簡稱KMP算法。KMP算法是字符串模式匹配中的經(jīng)典算法。和BF算法相比，KMP算法的不同點(diǎn)是匹配過程中，主串的位置指針不會(huì)回溯，這樣的結(jié)果使得算法時(shí)間復(fù)雜度只為O（n＋m）。

字符串匹配算法的使用（未完待整理）

字符串的匹配在Java中都知道使用indexOf函數(shù)來實(shí)現(xiàn)，那么其匹配算法是怎么樣的呢？

單模式和多模式的區(qū)別就是一次遍歷主串能否將多個(gè)模式的字符串都查找出來。

英文全稱為Brute Force，暴力匹配算法，匹配字符串的方法比較暴力，也比較簡單易懂。其大概的思路就是：

我們可以看到，在極端情況下，在主串 aaaa...aab 中尋找模式串 aab ，那么總共需要尋找(n-m+1)次，且每次都需要比對m次，那么時(shí)間復(fù)雜度將是 (n-m+1)*m ，即 O(n*m) ；但實(shí)際上并不會(huì)這么低效，因?yàn)槲覀兊氖褂脠鼍爸兄鞔湍Ｊ酱疾粫?huì)太長，而且在每個(gè)子串和模式串進(jìn)行比對時(shí)，只要中途有一個(gè)不匹配，那么當(dāng)前比對就會(huì)提前結(jié)束，因此大部分情況下，時(shí)間復(fù)雜度都會(huì)比 O(n*m) 要好。

我們在BF算法的基礎(chǔ)上引入哈希算法，我們不需要將每個(gè)子串與模式串逐個(gè)字符地進(jìn)行比較，而是計(jì)算得出每個(gè)子串的hash值，然后和模式串的hash值進(jìn)行比較，如果有相等的，那就說明有子串和模式串匹配上了。

雖然我們只需要比對模式串和子串的hash值就能得到匹配結(jié)果，次數(shù)為(n-m+1)，但是對每個(gè)子串進(jìn)行hash計(jì)算的時(shí)候，是要遍歷每個(gè)字符的，因此次數(shù)也是m，那么總的時(shí)間復(fù)雜度還是 O(n*m) ，并沒有明顯地提升。

那么我們該如何想出一個(gè)辦法，使得每個(gè)子串hash值的計(jì)算時(shí)間得到提升呢？這就是RK算法的精髓，假設(shè)子串包含的字符集中元素個(gè)數(shù)為k，那么就用k進(jìn)制數(shù)來代表這個(gè)子串，然后hash的過程就是將這個(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í)間開銷為 O(n)+O(1)*O(n-m+1) ，即為 O(n) ，時(shí)間復(fù)雜度比BF算法更加高效。

當(dāng)然，有hash的地方就有可能會(huì)存在hash沖突，有可能子串和hash值和模式串的hash值是一樣的，但內(nèi)容就是不一樣，此時(shí)怎么辦呢？其實(shí)很簡單，對于hash值一樣的子串，我們增加雙保險(xiǎn)，再比較一下這m個(gè)字符是否都一樣即可，總的時(shí)間開銷為 O(n)+O(1)*O(n-m+1)+O(m) ，即為 O(n) 。

如果極端情況下出現(xiàn)了很多hash沖突呢？我們對于每個(gè)和模式串相同hash值的子串都需要逐一再進(jìn)行比較，那么總的時(shí)間開銷就會(huì)為 O(n)+O(1)*O(n-m+1)+O(m)*O(n-m+1) ，即為 O(n*m) ，不過這種概率太小了，大部分情況下都不會(huì)這樣。

在真正的文本編輯器中查找和替換某個(gè)字符串時(shí)，使用的算法既不是上述的BF算法，也不是RK算法；BF算法只適合不是很長的主串，RK算法則要設(shè)計(jì)一個(gè)沖突概率很低的hash算法，這個(gè)比較困難，所以實(shí)際使用的是BM算法，它是工程中非常常用的一種字符串匹配算法，效率也是最高的。

算法的思想和過程有些復(fù)雜，待以后整理。

KMP算法在本質(zhì)上是和BM算法一樣的。算法的思想和過程有些復(fù)雜，待以后整理。

瀏覽器輸入框中的智能輸入匹配是怎么實(shí)現(xiàn)的，它是怎么做動(dòng)態(tài)字符串匹配查找的呢？這就用到了Trie樹。

又名字典樹，是一種專門用來快速查找字符串前綴匹配結(jié)果的樹形結(jié)構(gòu)，其本質(zhì)就是將所有字符串的重復(fù)的前綴合并在一起，構(gòu)造一個(gè)多叉樹。

其中，根節(jié)點(diǎn)不包含任何信息，每個(gè)節(jié)點(diǎn)表示一個(gè)字符，從根節(jié)點(diǎn)到紅色節(jié)點(diǎn)的一條路徑表示存儲(chǔ)的一個(gè)字符串。當(dāng)我們在如上Trie樹中查找"he"時(shí)，發(fā)現(xiàn)"he"并非是一個(gè)字符串，而是"hello"和"her"的公共前綴，那么就會(huì)找到這兩個(gè)字符串返回。

Trie樹在內(nèi)存中是如何存儲(chǔ)的呢？因?yàn)槊恳粋€(gè)節(jié)點(diǎn)都可能是包含所有字符的，所以每一個(gè)節(jié)點(diǎn)都是一個(gè)數(shù)組（或者散列表），用來存儲(chǔ)每個(gè)字符及其后綴節(jié)點(diǎn)的指針。

使用Trie樹，最開始構(gòu)建的時(shí)候，時(shí)間復(fù)雜度為 O(n) ，其中n為所有字符串長度之和，但是一旦構(gòu)建完成，頻繁地查詢某個(gè)字符串是非常高效的，時(shí)間復(fù)雜度為 O(k) ，其中k為查找字符串的長度。

Trie樹雖然查詢效率很高，但是比較浪費(fèi)內(nèi)存，每一個(gè)節(jié)點(diǎn)都必須維護(hù)一個(gè)數(shù)組存放所有可能的字符數(shù)據(jù)及其指向下一個(gè)節(jié)點(diǎn)的指針，因此在所有字符串公共前綴并不多的時(shí)候，內(nèi)存空間浪費(fèi)地就更多了。這種問題其實(shí)也有對應(yīng)的解決辦法，我們可以不使用數(shù)組，而是使用有序數(shù)組、散列表、紅黑樹來存放，可以相應(yīng)地降低性能來節(jié)省內(nèi)存空間。

Trie樹除了可以實(shí)現(xiàn)瀏覽器動(dòng)態(tài)輸入內(nèi)容查找候選項(xiàng)的功能外，還可以實(shí)現(xiàn)多模式地敏感詞匹配功能。假設(shè)我們需要對用戶輸入的內(nèi)容進(jìn)行敏感詞檢查，將所有的敏感內(nèi)容用***代替，那么該如何實(shí)現(xiàn)呢？

首先我們可以維護(hù)一個(gè)敏感詞字典，使用上述四種單模式匹配算法也可以實(shí)現(xiàn)，但是需要遍歷N次用戶輸入的內(nèi)容，其中N是所有敏感詞的模式串，顯得非常低效。但是我們?nèi)绻麑⒚舾性~字典維護(hù)為一個(gè)Trie樹，然后將用戶輸入的內(nèi)容從位置0開始在Trie樹中進(jìn)行查詢，如果匹配到紅色節(jié)點(diǎn)，那么說明有敏感詞；如果沒有匹配到紅色節(jié)點(diǎn)，就從用戶輸入內(nèi)容的下一個(gè)位置開始繼續(xù)在Trie樹中查詢，直至將用戶輸入內(nèi)容遍歷完，因此我們只是遍歷了一遍主串。

然而更高效的多模式字符串匹配使用地更多的是如下的AC自動(dòng)機(jī)。

如果把Trie樹比作BF算法，KMP算法是BF算法的改進(jìn)，那么AC自動(dòng)機(jī)就是利用同樣的思想改進(jìn)了Trie樹。

算法的思想和過程有些復(fù)雜，待以后整理。

求一個(gè)串中出現(xiàn)的第一個(gè)最長重復(fù)子串？

在編寫程序猿的時(shí)候，你需要仔細(xì)的去對照每一個(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)容測試結(jié)果

hello 1

java 1

sb 2

StringBuilder有多消耗性能

Java的String的indexOf方法性能最好，其次是KMP算法，其次是傳統(tǒng)的BF算法，當(dāng)然，對比有點(diǎn)牽強(qiáng)，SUN的算法也使用Java來實(shí)現(xiàn)、用的看著不像是KMP，還需要詳細(xì)研究一下。

測試代碼如下所示：

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算法完整代碼
標(biāo)題網(wǎng)址：http://aaarwkj.com/article40/dsiegho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供標(biāo)簽優(yōu)化、做網(wǎng)站、網(wǎng)頁設(shè)計(jì)公司、Google、網(wǎng)站導(dǎo)航、外貿(mào)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)