Aho-Corasick自动机的寻找周期

Question

我面临一个应该用Aho-Corasick自动机解决的问题。我给了一组单词（由'0'或'1'组成） - 模式，我必须决定是否可以创建无限文本，它不包含任何给定的模式。我认为，解决方案是创建Aho-Corasick自动机并搜索一个没有匹配状态的周期，但我无法提出一个好的方法来做到这一点。我想过使用DFS搜索状态图，但我不确定它是否会起作用，并且我有一个实现问题 - 让我们假设，我们处于一个'1'边的状态 - 但状态指出边缘被标记为匹配 - 因此我们不能使用该边缘，我们可以尝试失败链接（当前状态不具有'0'边缘） - 但是我们还必须记住，我们不能从指向状态的'1'边缘通过当前的失败链接。

任何人都可以纠正我，告诉我该怎么做？我用C++编写了Aho-Corasick，我确信它的工作原理 - 我也理解整个算法。

这是基础代码：

class AhoCorasick 
{ 

static const int ALPHABET_SIZE = 2; 

struct State 
{ 
    State* edge[ALPHABET_SIZE]; 
    State* fail; 
    State* longestMatchingSuffix; 
    //Vector used to remember which pattern matches in this state. 
    vector<int> matching; 
    short color; 

    State() 
    { 
    for(int i = 0; i < ALPHABET_SIZE; ++i) 
     edge[i] = 0; 
    color = 0; 
    } 

    ~State() 
    { 
    for(int i = 0; i < ALPHABET_SIZE; ++i) 
    { 
     delete edge[i]; 
    } 
    } 
}; 

private: 
    State root; 
    vector<int> lenOfPattern; 
    bool isFailComputed; 

    //Helper function used to traverse state graph. 
    State* move(State* curr, char letter) 
    { 
    while(curr != &root && curr->edge[letter] == 0) 
    { 
     curr = curr->fail; 
    } 
    if(curr->edge[letter] != 0) 
     curr = curr->edge[letter]; 
    return curr; 
    } 

    //Function which computes fail links and longestMatchingSuffix. 
    void computeFailLink() 
    { 
    queue< State* > Q; 
    root.fail = root.longestMatchingSuffix = 0; 
    for(int i = 0; i < ALPHABET_SIZE; ++i) 
    { 
     if(root.edge[i] != 0) 
     { 
     Q.push(root.edge[i]); 
     root.edge[i]->fail = &root; 
     } 
    } 
    while(!Q.empty()) 
    { 
     State* curr = Q.front(); 
     Q.pop(); 
     if(!curr->fail->matching.empty()) 
     { 
     curr->longestMatchingSuffix = curr->fail; 
     } 
     else 
     { 
     curr->longestMatchingSuffix = curr->fail->longestMatchingSuffix; 
     } 
     for(int i = 0; i < ALPHABET_SIZE; ++i) 
     { 
     if(curr->edge[i] != 0) 
     { 
      Q.push(curr->edge[i]); 
      State* state = curr->fail; 
      state = move(state, i); 
      curr->edge[i]->fail = state; 
     } 
     } 
    } 
    isFailComputed = true; 
    } 

public: 
    AhoCorasick() 
    { 
    isFailComputed = false; 
    } 

    //Add pattern to automaton. 
    //pattern - pointer to pattern, which will be added 
    //fun - function which will be used to transform character to 0-based index. 
    void addPattern(const char* const pattern, int (*fun) (const char *)) 
    { 
    isFailComputed = false; 
    int len = strlen(pattern); 
    State* curr = &root; 
    const char* pat = pattern; 
    for(; *pat; ++pat) 
    { 
     char tmpPat = fun(pat); 
     if(curr->edge[tmpPat] == 0) 
     { 
     curr = curr->edge[tmpPat] = new State; 
     } 
     else 
     { 
     curr = curr->edge[tmpPat]; 
     } 
    } 
    lenOfPattern.push_back(len); 
    curr->matching.push_back(lenOfPattern.size() - 1); 
    } 
}; 

int alphabet01(const char * c) 
{ 
    return *c - '0'; 
} 

Answer 1

我没有通过您的代码看，但我知道很简单，高效的实现。

首先，我们添加词典后缀链接到树（他们的描述，你可以在维基百科找到）。然后，你必须查看所有的树，并以某种方式标记具有Dict后缀链接的匹配节点和节点作为坏节点。这些行为的解释是显而易见的：您不需要所有匹配的节点或其中具有匹配后缀的节点。

现在你有一个没有任何匹配节点的Aho-Corasick树。如果你只是在生成的树上运行DFS算法，你会得到你想要的。