ACオートマトン(対象C++実装)

ACオートマトン(AC automatic)を使用して、TrieツリーTrieツリーとACオートマトンを組み合わせたデータ構造(複数のFailポインタのみ):

class Trie{
private:
size_t count;           //            
size_t flag;            //         
Trie* fail;             //  AC    Fail  
Trie **next;                //            
};

Trieツリーには、3つの基本演算ACオートマトンの挿入、検索、破棄が含まれています.Trieツリーの特性については、Failポインタ関数の構築とマルチモードマッチング関数の構築(Trieツリー実装、前の記事を参照)の意味用途がコード注釈に記載されています.

#include"Trie.h"
#include // BFS    Fail  
class ACAutomatic
{
public:
    explicit ACAutomatic(Trie *&_trie) : trie(_trie), typeCase(trie->typeCase) { makeFail(); }
    ACAutomatic() = delete;
    ~ACAutomatic() = default;
    /**
          Fail     ：
                  C，           ，        ，          C   。
                        C   。       root    ，         root。
　　  BFS(      )，         ，          。　　
    */
    void makeFail();
    /**
     root    ，                  。
　　      ，        ，       。          root  ，      ，       。
　　  AC                  ，             ，         ，       ，            。
    */
    int SearchACTrie(const std::string &strings) const;

private:
    Trie *≜
    TypeCase &typeCase;
    std::queue trieQueue;
};
inline void ACAutomatic::makeFail()
{
    auto root = trie;
    trie->fail = trie;
    trieQueue.push(trie);
    while (trieQueue.size() != 0)
    {
        auto rootNode = this->trieQueue.front();
        for (auto beg(0); beg < typeCase; ++beg) {
            if (rootNode->next[beg]) {
                trieQueue.push(rootNode->next[beg]);
                if (rootNode->fail->next[beg] && rootNode->fail->next[beg] != rootNode->next[beg])
                    rootNode->next[beg]->fail = rootNode->fail->next[beg];
                else rootNode->next[beg]->fail = rootNode->fail;
            }
        }
        trieQueue.pop();
    }
}
inline int ACAutomatic::SearchACTrie(const std::string &strings) const
{
    auto strIteratorToInt(0);
    auto triethis(trie);
    auto cnt(0);//        
    std::string::const_iterator stringBegin(strings.begin());
    std::string::const_iterator stringEnd(strings.end());
    while (stringBegin != stringEnd)
    {
        switch (typeCase)
        {
        case 2:  strIteratorToInt = static_cast(*stringBegin) - 48;//      
            if (strIteratorToInt < 0 || strIteratorToInt>1) return false;
            break;
        case 10:
            strIteratorToInt = static_cast(*stringBegin) - 48;//      
            if (strIteratorToInt < 0 || strIteratorToInt>9) return false;
            break;
        case 26:strIteratorToInt = static_cast(*stringBegin) - 97;//      
            if (strIteratorToInt < 0 || strIteratorToInt>26) return false;
            break;
        default:return false;
        }
        if (triethis->next[strIteratorToInt]) {
            triethis = triethis->next[strIteratorToInt];
            if (triethis->flag)  
                cnt+= triethis->flag;           
        }
        else {
            triethis = triethis->fail;
            if(triethis->next[strIteratorToInt])
                triethis = triethis->next[strIteratorToInt];
            if (triethis->flag)
                cnt += triethis->flag;
        }
        ++stringBegin;
    }
    return cnt;
}

例:yasherhsでsay、she、shr、her、shに含まれる個数(sherとherの2つの単語を含む)を検索します.

#include
#include"Trie.h"
#include"ACAutomatic.h"
int main()
{
    auto trie = new Trie(LowerCase);//  Trie ，           
    std::cout << trie->InsertTrie("say");//      true
    std::cout << trie->InsertTrie("she");//      true
    std::cout << trie->InsertTrie("shr");//      true
    std::cout << trie->InsertTrie("her");//      true
    std::cout << trie->InsertTrie("sh");//      true
    std::cout << std::endl;
    auto acautomatic = new ACAutomatic(trie);//   AC   
    std::cout<SearchACTrie("yasherhs");//            
    return 0;
}

出力:11111 3