0

此代码适用于我从此处引用的 Aho-Corasick 算法

我理解这段代码直到 push_links 方法的 if 块，但我没有得到相同方法的 else 部分的用途或要求。更具体地说，第一种方法用于构建 trie。剩下的工作是通过第二种方法完成的，即将节点链接到它们最长的正确后缀，这些后缀也是某种模式的前缀。这是由 If 块执行的，那么 else 部分需要什么。

请帮助我。

const int MAXN = 404, MOD = 1e9 + 7, sigma = 26;

int term[MAXN], len[MAXN], to[MAXN][sigma], link[MAXN], sz = 1;    

  // this method is for constructing trie

void add_str(string s)    
{ 

  // here cur denotes current node   

  int cur = 0;    

  // this for loop adds string to trie character by character

  for(auto c: s)        
    {     
      if(!to[cur][c - 'a'])  
        {   

  //here two nodes or characters are linked using transition                                       
  //array "to"

         to[cur][c - 'a'] = sz++;  
         len[to[cur][c - 'a']] = len[cur] + 1;     

         }

  // for updating the current node  

       cur = to[cur][c - 'a'];  
    }

  //for marking the leaf nodes or terminals

   term[cur] = cur;   
}   


void push_links()  
{
 //here queue is used for breadth first search of the trie  
 int que[sz];  
 int st = 0, fi = 1;  

 //very first node is enqueued 
 que[0] = 0;   

 while(st < fi)  
   { 

 // here nodes in the queue are dequeued  
    int V = que[st++];  

 // link[] array contains the suffix links.
    int U = link[V];


    if(!term[V]) term[V] = term[U];   

  // here links for the other nodes are find out using assumption that the  
  // link for the parent node is defined    

   for(int c = 0; c < sigma; c++)   

   // this if condition ensures that transition is possible to the next node 
   // for input 'c' 

        if(to[V][c])    
        {   

   // for the possible transitions link to the reached node is assigned over 
   // here which is nothing but transition on input 'c' from the link of the 
   // current node

            link[to[V][c]] = V ? to[U][c] : 0;  
            que[fi++] = to[V][c];  
        }  
        else 
        {  
            to[V][c] = to[U][c];  
        }  
   }  
}
4

2 回答 2

1

IMO 你不需要 else 条件。如果没有孩子，要么它已经是一个链接，要么什么都没有。

于 2015-06-13T08:53:17.893 回答
0

Aho-Corasick 算法有一些变体。基本算法假设如果当前节点 ( cur ) 与符号 ( c ) 的边缺失，则您通过后缀链接前往第一个具有c边的节点（您通过此边移动）。但是您对后缀链接的方式是相同的（来自相同的cur和c），因为您在搜索时不会更改自动机。所以你可以缓存它（保存结果

// start from node 
while (parent of node doesn't have an edge over c) {
  node = parent
}
// set trie position
node = to[node][c]
// go to next character

在 [节点] [c] 中。所以下次你不会再这样做了。并且它从非确定性自动机转变为确定性状态机（推送后不必使用链接数组，只能使用数组）。

这个实现存在一些问题。首先，您可以获得找到的字符串的索引（您不保存它）。此外， len 数组不在任何地方使用。

为了

意思是，这个算法只是使用“link[to[V][c]] = V ? to[U][c] : 0;”来检查当前节点链接中的字符是否存在。不应该在父母链接中验证吗？

是的，没关系，因为如果 to[U][c] 为 0，那么所有链 U->suffix_parent->suffix_parent ... -> root = 0 中都没有通过 c 的边。所以你应该设置到[V][c] 到零。

于 2015-06-16T23:20:04.230 回答