Зачем нужен блок else в методе "push_links" следующего кода?

Question

Этот код для алгоритма Aho-Corasick, который я отсюда рецензировал

Я понял этот код до блока if метода push_links, но я не получил использование или требование для остальной части того же метода. Более конкретно, первый метод используется для построения дерева. Оставшаяся работа выполняется вторым методом, т.е. связывает узел с их самым длинным надлежащим суффиксом, который также является префиксом некоторого шаблона. Это выполняется блоком If, тогда зачем нужна другая часть.

Пожалуйста, помогите мне в этом.

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];  
        }  
   }  
}

Answer 1

ИМО тебе не нужно другое условие. Если нет детей, то это либо ссылка, либо ничего.

Answer 2

Есть несколько вариантов алгоритма 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

в [узел] [с]. Так что в следующий раз вы не будете делать это снова. И это превращает автомат из недетерминированного в детерминированный конечный автомат (вы не должны использовать массив ссылок после нажатия, вы можете использовать только для массива).

Есть некоторые проблемы с этой реализацией. Во-первых, вы можете получить индекс найденной строки (вы не сохраняете его). Кроме того, массив len нигде не используется.

За

означает, что этот алгоритм просто проверяет наличие символа в текущей ссылке на узел, используя "link[to[V][c]] = V? to[U][c]: 0;". не должно ли это проверить в родителях ссылку тоже?

Да, все в порядке, потому что если [U] [c] равно 0, то нет никаких ребер через c из всей цепочки U-> суффикс_парент-> суффикс родительского суффикса_парента... -> root = 0. Поэтому вы должны установить до [V] [с] до нуля.