一窥淆、如何實(shí)現(xiàn)敏感詞過(guò)濾：

1、基于單模式串實(shí)現(xiàn)的敏感詞過(guò)濾：

<1>滤灯、單模式串匹配算法：

??是在一個(gè)模式串和一個(gè)主串之間進(jìn)行匹配坪稽，也就是說(shuō)，在一個(gè)主串中查找一個(gè)模式串鳞骤。BF算法窒百、 RK算法、 BM算法豫尽、 KMP算法都是單模式匹配算法篙梢。

<2>、基于單模式串實(shí)現(xiàn)敏感詞過(guò)濾的方法：

??針對(duì)每個(gè)敏感詞拂募，通過(guò)單模式串匹配算法（比如KMP算法）與用戶輸入的文字內(nèi)容進(jìn)行匹配庭猩。但是，這樣做的話陈症，每個(gè)匹配過(guò)程都需要掃描一遍用戶輸入的內(nèi)容蔼水。整個(gè)過(guò)程下來(lái)就要掃描很多遍用戶輸入的內(nèi)容。如果敏感詞很多录肯，比如幾千個(gè)趴腋，并且用戶輸入的內(nèi)容很長(zhǎng)，假如有上千個(gè)字符论咏，那我們就需要掃描幾千遍這樣的輸入內(nèi)容优炬。很顯然，這種處理思路比較低效厅贪。

2蠢护、基于Trie樹實(shí)現(xiàn)的敏感詞過(guò)濾：

<1>、多模式串匹配算法：

??是在多個(gè)模式串和一個(gè)主串之間做匹配养涮，也就是說(shuō)葵硕，在一個(gè)主串中查找多個(gè)模式串。Trie樹是多模式匹配算法贯吓。

<2>懈凹、基于Trie樹實(shí)現(xiàn)敏感詞過(guò)濾的方法：

??對(duì)敏感詞字典進(jìn)行預(yù)處理，構(gòu)建成Trie樹結(jié)構(gòu)悄谐。這個(gè)預(yù)處理的操作只需要做一次介评，如果敏感詞字典動(dòng)態(tài)更新了，比如刪除爬舰、添加了一個(gè)敏感詞们陆，只需要?jiǎng)討B(tài)更新一下Trie樹即可寒瓦。當(dāng)用戶輸入一個(gè)文本內(nèi)容后，把用戶輸入的內(nèi)容作為主串棒掠，從第一個(gè)字符（假設(shè)是字符C）開始孵构，在Trie樹中匹配。當(dāng)匹配到Trie樹的葉子節(jié)點(diǎn)烟很，或者中途遇到不匹配字符的時(shí)候，將主串的開始匹配位置后移一位蜡镶，也就是從字符C的下一個(gè)字符開始雾袱，重新在Trie樹中匹配。

二官还、AC自動(dòng)機(jī)：

1芹橡、AC自動(dòng)機(jī)概念：

??AC自動(dòng)機(jī)算法，全稱是Aho-Corasick算法望伦。其實(shí)林说， Trie樹跟AC自動(dòng)機(jī)之間的關(guān)系，就像單串匹配中樸素的串匹配算法屯伞，跟KMP算法之間的關(guān)系一樣腿箩，只不過(guò)前者針對(duì)的是多模式串而已。所以劣摇， AC自動(dòng)機(jī)實(shí)際上就是在Trie樹之上珠移，加了類似KMP的next數(shù)組，只不過(guò)此處的next數(shù)組是構(gòu)建在樹上罷了末融。

2钧惧、AC自動(dòng)機(jī)的代碼表示：

public class AcNode {
    public char data;
    public AcNode[] children = new AcNode[26]; // 字符集只包含a~z這26個(gè)字符
    public boolean isEndingChar = false; // 結(jié)尾字符為true
    public int length = -1; // 當(dāng)isEndingChar=true時(shí)，記錄模式串長(zhǎng)度
    public AcNode fail; // 失敗指針
    public AcNode(char data) {
        this.data = data;
    }
}

3勾习、AC自動(dòng)機(jī)的構(gòu)建操作：

• 將多個(gè)模式串構(gòu)建成Trie樹浓瞪；
• 在Trie樹上構(gòu)建失敗指針（相當(dāng)于KMP中的失效函數(shù)next數(shù)組）。

4巧婶、AC自動(dòng)機(jī)構(gòu)建失敗指針的方法：

<1>乾颁、構(gòu)建思路：

假設(shè)這里有4個(gè)模式串，分別是c粹舵， bc钮孵， bcd， abcd眼滤；主串是abcd巴席。

<2>坝咐、構(gòu)建代碼：

public void buildFailurePointer() {
    Queue<AcNode> queue = new LinkedList<>();
    root.fail = null;
    queue.add(root);
    while (!queue.isEmpty()) {
        AcNode p = queue.remove();
        for (int i = 0; i < 26; ++i) {
            AcNode pc = p.children[i];
            if (pc == null) continue;
            if (p == root) {
                pc.fail = root;
            } else {
                AcNode q = p.fail;
                while (q != null) {
                    AcNode qc = q.children[pc.data - 'a'];
                    if (qc != null) {
                        pc.fail = qc;
                        break;
                    }
                    q = q.fail;
                }
                if (q == null) {
                    pc.fail = root;
                }
            }
            queue.add(pc);
        }
    }
}

5、在AC自動(dòng)機(jī)上匹配主串的方法：

<1>析恢、原理：

??在匹配過(guò)程中墨坚，主串從i=0開始， AC自動(dòng)機(jī)從指針p=root開始映挂，假設(shè)模式串是b泽篮，主串是a。

• 如果p指向的節(jié)點(diǎn)有一個(gè)等于b[i]的子節(jié)點(diǎn)x袖肥，就更新p指向x咪辱，這個(gè)時(shí)候需要通過(guò)失敗指針，檢測(cè)一系列失敗指針為結(jié)尾的路徑是否是模式串椎组。處理完之后，將i加一历恐，繼續(xù)這兩個(gè)過(guò)程寸癌；
• 如果p指向的節(jié)點(diǎn)沒(méi)有等于b[i]的子節(jié)點(diǎn)，讓p=p->fail弱贼，然后繼續(xù)這兩個(gè)過(guò)程蒸苇。

<2>、代碼：

public void match(char[] text) { // text是主串
    int n = text.length;
    AcNode p = root;
    for (int i = 0; i < n; ++i) {
        int idx = text[i] - 'a';
        while (p.children[idx] == null && p != root) {
            p = p.fail; // 失敗指針發(fā)揮作用的地方
        }
        p = p.children[idx];
        if (p == null) p = root; // 如果沒(méi)有匹配的吮旅，從root開始重新匹配
        AcNode tmp = p;
        while (tmp != root) { // 打印出可以匹配的模式串
            if (tmp.isEndingChar == true) {
                int pos = i-tmp.length+1;
                System.out.println("匹配起始下標(biāo)" + pos + "; 長(zhǎng)度" + tmp.length);
            }
            tmp = tmp.fail;
        }
    }
}