0

我正面临一个应该使用 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';
}
4

1 回答 1

0

我没有看你的代码，但我知道非常简单有效的实现。

首先，让我们将字典后缀链接添加到树中（您可以在 Wikipedia 中找到它们的描述）。然后，您必须查看所有树并以某种方式将匹配节点和具有 Dict 后缀链接的节点标记为坏节点。这些动作的解释很明显：您不需要所有匹配的节点，或者其中包含匹配后缀的节点。

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

于 2013-03-26T17:56:13.820 回答