aho-corasick 알고리즘을 사용하여 충돌이 발생 했습니까?

여기에 aho-corasick 알고리즘에 대한 코드가 있습니다 : http://www.komodia.com/aho-corasick.aho-corasick 알고리즘을 사용하여 충돌이 발생 했습니까?

가이드로 사용하여 선을 추가하고 트리를 만들었습니다.

그러나 std 문자열을 std 문자열로 변경했으나 중요하지 않습니다. 방금 typedef를 변경했습니다.

내가 사용하고 검색 할 때 결과가 없으면 아무런 문제가 없습니다. 결과를 찾으면 표준 예외 범위를 벗어납니다.

그것은 여기에 충돌 :

 if (aIterator==pNode->aMap.end()) 
      //No, check if we have failure node 
      if (!pNode->pFailureNode) 
      { 
       //No failure node, start at root again 
       pNode=&m_aRoot; 

       //Reset search string 
       sMatchedString=""; 

       //Did we do a switch? 
       if (bSwitch) 
        //We need to do this over 
        --iCount; 

       //Exit this loop 
       break; 
      } 
      else 
      { 
       //What is the depth difference? 
       unsigned short usDepth; 
       usDepth=pNode->usDepth-pNode->pFailureNode->usDepth-1; 

       //This is how many chars to remove 
       sMatchedString=sMatchedString.substr(usDepth,sMatchedString.length()-usDepth); //CRASHES HERE!! 

       //Go to the failure node 
       pNode=pNode->pFailureNode; 

       //Set to switch 
       bSwitch=true; 
      } 
     else 
     { 
      //Add the char 
      sMatchedString+=rString[iCount]; 

      //Save the new node 
      pNode=aIterator->second; 

      //Exit the loop 
      break; 
     } 
    }

그것은 여기 충돌 : 여기

sMatchedString=sMatchedString.substr(usDepth,sMatchedString.length()-usDepth);

이 변수 :이은에 검열을 구현하기 위해 사용하고

enter image description here

경기.

무엇이 충돌 할 수 있습니까?

두 번 추가 한 문자열이 있는데 문제가 될 수 있습니까?

감사

출처

2012-06-05 jmasterx

투표의 마감 : 낯선 사람에게 검사하여 코드의 오류를 찾아내는 것은 생산성이 떨어집니다. 디버거 나 print 문을 사용하여 문제를 확인 (또는 적어도 격리) 한 다음보다 구체적인 질문으로 돌아 가야합니다 (10 줄 [테스트 케이스] (http : /sscce.org)). –

하나의 가능성이 문제는 usDepth이 -2의 길이 (한 문자열에서) 세 번째 문자에서 문자열을 초래 3. 동안 sMatchedString이 "u" 것입니다.

출처

2012-06-05 06:33:19

aho-corasick 알고리즘을 사용하여 충돌이 발생 했습니까?

답변

관련 문제