【模式匹配】之——多模匹配 下篇（AC算法之前缀树实现）

#include "Trie.h" int CTrie::m_nID = 1; CTrie::CTrie(void) { m_root.nID = 0; m_root.ch = '?'; m_root.nDeep = 0; m_nMaxPatternLen = 0; m_pStr = NULL; } CTrie::~CTrie(void) { if (m_pStr) { delete m_pStr; m_pStr = NULL; } ReleaseTrie(); } void CTrie::ShowTrie() { ShowNode(&m_root); } void CTrie::ShowNode(NODE *pNode) { printf("=================================================================\r\n"); printf("ID (%2d) \"%c\", depth =%2d, ", pNode->nID, pNode->ch, pNode->nDeep); printf("Failure node = (%2d). |<%2d> - ", pNode->failureNode->nID, pNode->nID); if (0 != pNode->vecNode.size()) { printf("Children:"); } for (unsigned int i = 0; i < pNode->vecNode.size(); i++) { printf("(%2d) ", pNode->vecNode[i]->nID); } if (0 != pNode->vecMatchPattern.size()) { printf("Match pattern: "); } for (unsigned int i = 0; i < pNode->vecMatchPattern.size(); i++) { printf("\"%s\" ", pNode->vecMatchPattern[i]); } printf("\r\n"); for (unsigned int i = 0; i < pNode->vecNode.size(); i++) { ShowNode(pNode->vecNode[i]); } } bool CTrie::Create(const MY_PATTERN pattern[], int nCount) { bool bRet = false; ReleaseTrie(); for (int i = 0; i < nCount; i++) { if (pattern[i].nLen > m_nMaxPatternLen) { m_nMaxPatternLen = pattern[i].nLen; } NODE *where = &m_root; bool isNeedFind = true; for (int j = 0; j < pattern[i].nLen; j++) { char ch = pattern[i].p[j]; NODE *find = NULL; if (isNeedFind && (find = FindNode(where, ch))) { where = find; } else { isNeedFind = false; NODE *pNode = new NODE; if (!pNode) { return false; } pNode->ch = ch; InsertNode(where, pNode); where = pNode; } if (j == pattern[i].nLen - 1) { where->vecMatchPattern.push_back(pattern[i].p); } } } bRet = SetFailure(); if (bRet) { SetMatchPattern(&m_root); } return bRet; } void CTrie::InsertNode(NODE *where, PNODE pnode) { pnode->nID = m_nID++; pnode->nDeep = where->nDeep + 1; where->vecNode.push_back(pnode); } NODE* CTrie::FindNode(NODE* where, char ch) { for (unsigned int i = 0; i < where->vecNode.size(); i++) { if (where->vecNode[i]->ch == ch) { return where->vecNode[i]; } } return NULL; } bool CTrie::SetFailure() { m_pStr = new char[m_nMaxPatternLen + 1];//the root occupy 1 byte if (!m_pStr) { return false; } SetFailureNode(&m_root); return true; } void CTrie::SetFailureNode(NODE *pNode) { m_pStr[pNode->nDeep] = pNode->ch; //find the max length prefix match the suffix, and the right char of them is not same NODE *pFind = &m_root; for (int i = 2; i <= pNode->nDeep; i++) { for (int j = i; j <= pNode->nDeep && pFind; j++) { pFind = FindNode(pFind, m_pStr[j]); } if (pFind && pFind != &m_root && CheckChilrenContain(pNode, pFind)) { break; } pFind = &m_root; } pNode->failureNode = pFind; for (unsigned int i = 0; i < pNode->vecNode.size(); i++) { SetFailureNode(pNode->vecNode[i]); } } void CTrie::ReleaseTrie() { ReleaseNode(&m_root); } void CTrie::ReleaseNode(NODE *pNode) { for (unsigned int i = 0; i < pNode->vecNode.size(); i++ ) { ReleaseNode(pNode->vecNode[i]); } pNode->vecNode.clear(); if (pNode != &m_root) { delete pNode; } m_nID = 1; } // Check the node that are pFind's children is not the pNode's children // If one of the pFind's children is not the pNode's children, return true // If all of the pFind's children is pNode's children also, return false // If pFind or pNode no child, return true bool CTrie::CheckChilrenContain(NODE *pNode, NODE *pFind) { return true;// if check this, the pattern like "aaaa", "aaa", "aa", can not report full if (0 == pNode->vecNode.size() || 0 == pFind->vecNode.size()) { return true; } for (unsigned int i = 0; i < pFind->vecNode.size(); i++) { NODE *p = pFind->vecNode[i]; bool isFind = false; for (unsigned int j = 0; j < pNode->vecNode.size(); j++) { if (p->ch == pNode->vecNode[j]->ch) { isFind = true; break; } } if (false == isFind) { return true; } } return false; } bool CTrie::Search(char *pDest, int nLen) { NODE *pCur = &m_root; NODE *pFind = NULL; for (int i = 0; i < nLen; i++) { if (pFind = FindNode(pCur, pDest[i])) { pCur = pFind; if (0 != pCur->vecMatchPattern.size()) { ReportMatch(pCur, i); } } else { if (pCur != &m_root) { pCur = pCur->failureNode; i--; } } } return true; } void CTrie::SetMatchPattern(NODE *pNode) { NODE *pCur = pNode; while (&m_root != (pCur = pCur->failureNode)) { for (unsigned int i = 0; i < pCur->vecMatchPattern.size(); i++) { pNode->vecMatchPattern.push_back(pCur->vecMatchPattern[i]); } if (pCur->vecMatchPattern.size() > 1)//the failure node has been collected all match pattern { break; } } for (unsigned int i = 0; i < pNode->vecNode.size(); i++) { SetMatchPattern(pNode->vecNode[i]); } } bool CTrie::ReportMatch(NODE *pNode, int nPos) { printf("Match pattern at %d:\r\n", nPos); for (unsigned int i = 0; i < pNode->vecMatchPattern.size(); i++) { printf(" \"%s\"\r\n", pNode->vecMatchPattern[i]); } return true; }