Unhandled exception at 0x76acfbae in AC.exe: Microsoft C++ exception: std::out_of_range at memory location 0x0015a140.. "
Any advice on how to handle this error?
I checked the memory , the program use almost 1GB of the memory of 2GB RAM....So its not the memory.....
CSuffixTrie.h
<pre>#if !defined(AFX_SUFFIXTRIE_H__34D2D872_1C59_4D9F_BAF1_6AB80D7333B1__INCLUDED_)
#define AFX_SUFFIXTRIE_H__34D2D872_1C59_4D9F_BAF1_6AB80D7333B1__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#pragma warning(disable:4786)
#include <map>
#include <string>
#include <vector>
#include <set>
class CSuffixTrie
{
public:
typedef std::wstring SearchString;
typedef struct _DataFound
{
int iFoundPosition;
SearchString sDataFound;
} DataFound;
typedef std::vector<datafound> DataFoundVector;
typedef std::vector<searchstring> StringsVector;
typedef std::set<searchstring> StringsSet;
public:
StringsVector GetAllStringsVector()const;
StringsSet GetAllStringsSet()const;
void Clear();
void BuildTreeIndex();
void AddString(const SearchString& rString);
bool FindString(const SearchString& rString)const;
void DeleteString(const SearchString& rString);
DataFound SearchAhoCorasik(const SearchString& rString)const;
DataFoundVector SearchAhoCorasikMultiple(const SearchString& rString)const;
CSuffixTrie& operator=(const CSuffixTrie& rTrie);
CSuffixTrie();
CSuffixTrie(const CSuffixTrie& rTrie);
virtual ~CSuffixTrie();
private:
typedef wchar_t SearchChar;
struct _Node;
typedef std::map <SearchChar,_Node*> SearchMap;
typedef struct _Node
{
SearchChar aChar;
bool bFinal;
SearchMap aMap;
_Node* pFailureNode;
unsigned short usDepth;
} Node;
private:
void AddString(const SearchString& rString,
Node* pNode);
const Node* SearchNode(const SearchString& rString,
const Node* pNode)const;
Node* SearchNode(const SearchString& rString,
Node* pNode);
void BuildIndex(const SearchString& rString,
Node* pNode);
void DeleteNode(Node* pNode)const;
Node* CloneNode(const Node* pNode)const;
void CloneTrie(CSuffixTrie& rTarget)const;
void BuildStrings(StringsVector& rVector,
const SearchString& rString,
const Node* pNode)const;
Node m_aRoot;
};
#endif // !defined(AFX_SUFFIXTRIE_H__34D2D872_1C59_4D9F_BAF1_6AB80D7333B1__INCLUDED_)
</searchstring></searchstring></datafound></set></vector></string>
CSuffixTrie.cpp
#include "stdafx.h"
#include "SuffixTrie.h"
CSuffixTrie::CSuffixTrie()
{
m_aRoot.pFailureNode=NULL;
m_aRoot.aChar=0;
m_aRoot.bFinal=false;
m_aRoot.usDepth=0;
}
CSuffixTrie::CSuffixTrie(const CSuffixTrie& rTrie)
{
rTrie.CloneTrie(*this);
}
CSuffixTrie::~CSuffixTrie()
{
Clear();
}
void CSuffixTrie::Clear()
{
DeleteNode(&m_aRoot);
}
CSuffixTrie& CSuffixTrie::operator=(const CSuffixTrie& rTrie)
{
if (this==&rTrie)
return *this;
rTrie.CloneTrie(*this);
return *this;
}
void CSuffixTrie::CloneTrie(CSuffixTrie& rTarget)const
{
rTarget.Clear();
Node* pClone;
pClone=CloneNode(&m_aRoot);
rTarget.m_aRoot=*pClone;
rTarget.BuildTreeIndex();
delete pClone;
}
void CSuffixTrie::AddString(const SearchString& rString)
{
AddString(rString,
&m_aRoot);
}
void CSuffixTrie::AddString(const SearchString& rString,
Node* pNode)
{
if (!pNode ||
rString.empty())
return;
SearchChar aChar;
aChar=rString[0];
SearchMap::iterator aIterator;
aIterator=pNode->aMap.find(aChar);
Node* pNewNode;
if (aIterator==pNode->aMap.end())
{
pNewNode=new Node;
pNewNode->pFailureNode=NULL;
pNewNode->aChar=aChar;
pNewNode->usDepth=pNode->usDepth+1;
pNewNode->bFinal=false;
pNode->aMap.insert(SearchMap::value_type(aChar,pNewNode));
}
else
pNewNode=aIterator->second;
if (rString.length()==1)
pNewNode->bFinal=true;
else
AddString(rString.substr(1,rString.length()-1),
pNewNode);
}
void CSuffixTrie::DeleteNode(Node* pNode)const
{
if (!pNode)
return;
for (SearchMap::iterator aIterator=pNode->aMap.begin();
aIterator!=pNode->aMap.end();
++aIterator)
{
DeleteNode(aIterator->second);
delete aIterator->second;
}
}
void CSuffixTrie::BuildTreeIndex()
{
BuildIndex(L"",
&m_aRoot);
}
CSuffixTrie::Node* CSuffixTrie::SearchNode(const SearchString& rString,
Node* pNode)
{
if (!pNode ||
rString.empty())
return NULL;
SearchChar aChar;
aChar=rString[0];
SearchMap::iterator aIterator;
aIterator=pNode->aMap.find(aChar);
if (aIterator!=pNode->aMap.end())
{
if (rString.length()==1)
return aIterator->second;
else
return SearchNode(rString.substr(1,rString.length()-1),
aIterator->second);
}
else
return NULL;
}
const CSuffixTrie::Node* CSuffixTrie::SearchNode(const SearchString& rString,
const Node* pNode)const
{
if (!pNode ||
rString.empty())
return NULL;
SearchChar aChar;
aChar=rString[0];
SearchMap::const_iterator aIterator;
aIterator=pNode->aMap.find(aChar);
if (aIterator!=pNode->aMap.end())
{
if (rString.length()==1)
return aIterator->second;
else
return SearchNode(rString.substr(1,rString.length()-1),
aIterator->second);
}
else
return NULL;
}
void CSuffixTrie::BuildIndex(const SearchString& rString,
Node* pNode)
{
if (!pNode)
return;
if (pNode->usDepth>1)
{
pNode->pFailureNode=NULL;
for (int iCount=1;
iCount<rString.length();
++iCount)
{
SearchString sString;
sString=rString.substr(iCount,rString.length()-iCount);
Node* pFoundNode;
pFoundNode=SearchNode(sString,
&m_aRoot);
if (pFoundNode)
{
pNode->pFailureNode=pFoundNode;
break;
}
}
}
SearchString sString(rString);
for (SearchMap::iterator aIterator=pNode->aMap.begin();
aIterator!=pNode->aMap.end();
++aIterator)
BuildIndex(rString+aIterator->first,
aIterator->second);
}
CSuffixTrie::DataFound CSuffixTrie::SearchAhoCorasik(const SearchString& rString)const
{
DataFound aData;
aData.iFoundPosition=0;
SearchString sMatchedString;
const Node* pNode;
pNode=&m_aRoot;
for (int iCount=0;
iCount<rstring.length();>
++iCount)
{
bool bSwitch;
bSwitch=false;
while (1)
{
SearchMap::const_iterator aIterator;
aIterator=pNode->aMap.find(rString[iCount]);
if (aIterator==pNode->aMap.end())
if (!pNode->pFailureNode)
{
pNode=&m_aRoot;
sMatchedString=L"";
if (bSwitch)
--iCount;
break;
}
else
{
unsigned short usDepth;
usDepth=pNode->usDepth-pNode->pFailureNode->usDepth-1;
sMatchedString=sMatchedString.substr(usDepth,sMatchedString.length()-usDepth);
pNode=pNode->pFailureNode;
bSwitch=true;
}
else
{
sMatchedString+=rString[iCount];
pNode=aIterator->second;
break;
}
}
if (pNode->bFinal)
{
aData.iFoundPosition=iCount-sMatchedString.length()+1;
aData.sDataFound=sMatchedString;
return aData;
}
}
return aData;
}
CSuffixTrie::DataFoundVector CSuffixTrie::SearchAhoCorasikMultiple(const SearchString& rString)const
{
DataFoundVector aVec;
SearchString sMatchedString;
const Node* pNode;
pNode=&m_aRoot;
for (int iCount=0;
iCount < rString.length();
++iCount)
{
bool bSwitch;
bSwitch=false;
while (1)
{
SearchMap::const_iterator aIterator;
aIterator=pNode->aMap.find(rString[iCount]);
if (aIterator==pNode->aMap.end())
if (!pNode->pFailureNode)
{
pNode=&m_aRoot;
sMatchedString=L"";
if (bSwitch)
--iCount;
break;
}
else
{
unsigned short usDepth;
usDepth=pNode->usDepth-pNode->pFailureNode->usDepth-1;
sMatchedString=sMatchedString.substr(usDepth,sMatchedString.length()-usDepth);
pNode=pNode->pFailureNode;
bSwitch=true;
}
else
{
sMatchedString+=rString[iCount];
pNode=aIterator->second;
break;
}
}
if (pNode->bFinal)
{
DataFound aData;
aData.iFoundPosition=iCount-sMatchedString.length()+1;
aData.sDataFound=sMatchedString;
aVec.push_back(aData);
iCount-=sMatchedString.length()-1;
sMatchedString=L"";
}
}
return aVec;
}
CSuffixTrie::Node* CSuffixTrie::CloneNode(const Node* pNode)const
{
if (!pNode)
return NULL;
Node* pNewNode;
pNewNode=new Node;
pNewNode->aChar=pNode->aChar;
pNewNode->bFinal=pNode->bFinal;
pNewNode->pFailureNode=NULL;
pNewNode->usDepth=pNode->usDepth;
for (SearchMap::const_iterator aIterator=pNode->aMap.begin();
aIterator!=pNode->aMap.end();
++aIterator)
{
Node* pSubNode;
pSubNode=CloneNode(aIterator->second);
if (pSubNode)
pNewNode->aMap.insert(SearchMap::value_type(aIterator->first,pSubNode));
}
return pNewNode;
}
bool CSuffixTrie::FindString(const SearchString& rString)const
{
return SearchNode(rString,
&m_aRoot)!=NULL;
}
CSuffixTrie::StringsVector CSuffixTrie::GetAllStringsVector()const
{
StringsVector aVector;
BuildStrings(aVector,
L"",
&m_aRoot);
return aVector;
}
CSuffixTrie::StringsSet CSuffixTrie::GetAllStringsSet()const
{
StringsVector aVector(GetAllStringsVector());
StringsSet aSet;
for (int iCount=0;
iCount < aVector.size();
++iCount)
aSet.insert(aVector[iCount]);
return aSet;
}
void CSuffixTrie::BuildStrings(StringsVector& rVector,
const SearchString& rString,
const Node* pNode)const
{
if (!pNode)
return;
if (pNode->bFinal)
rVector.push_back(rString);
for (SearchMap::const_iterator aIterator=pNode->aMap.begin();
aIterator!=pNode->aMap.end();
++aIterator)
BuildStrings(rVector,
rString+aIterator->first,
aIterator->second);
}
void CSuffixTrie::DeleteString(const SearchString& rString)
{
Node* pPrevNode;
pPrevNode=NULL;
for (int iCount=0;
iCount<rString.length();
++iCount)
{
Node* pNode;
pNode=SearchNode(rString.substr(iCount,rString.length()-iCount),
&m_aRoot);
if (pPrevNode && pNode)
{
pNode->aMap.erase(pPrevNode->aChar);
delete pPrevNode;
pPrevNode=NULL;
}
if (pNode)
if (!iCount)
if (pNode->aMap.empty())
pPrevNode=pNode;
else
{
pNode->bFinal=false;
return;
}
else if (pNode->aMap.empty())
pPrevNode=pNode;
else
return;
}
}
main()
#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#include "SuffixTrie.h"
#include <fstream>
#include <iostream>
#include <string>
#include <ctime>
using namespace std;
void AC_search(string textx,string patternx)
{
CSuffixTrie aTree;
CSuffixTrie::_DataFound aData;
CSuffixTrie::DataFoundVector aDataFound;
ifstream inFile1, inFile2;
string pattern,text,line;
wchar_t NameBuffer[10000];
char *T;
T = new char[10000];
char *p;
p = new char[500];
pattern=patternx;
inFile1.open(pattern.c_str());
if ( !inFile1 )
{
cout<<"Unable to open file. Enter a different name: ";
inFile1.clear();
cin << pattern;
inFile1.open(pattern.c_str());
}
text=textx;
inFile2.open(text.c_str());
if ( !inFile2 )
{
cout<<"Unable to open file. Enter a different name: ";
inFile2.clear();
cin >> text;
inFile2.open(text.c_str());
}
while(getline(inFile1, line))
{
strcpy_s(p, 500, line.c_str());
cout<<p<<endl;
string search = p;
const size_t newsize = 100;
size_t origsize = strlen(search.c_str()) + 1;
size_t convertedChars = 0;
wchar_t wcstring[newsize];
mbstowcs( wcstring, search.c_str(), newsize);
aTree.AddString(wcstring);
}
aTree.BuildTreeIndex();
while(getline(inFile2, line))
{
strcpy_s(T, 500, line.c_str());
cout<<T<<endl;
string search1 = T;
const size_t newsize1 = 500;
size_t origsize = strlen(search1.c_str()) + 1;
size_t convertedChars = 0;
wchar_t wcstring1[newsize1];
mbstowcs( wcstring1, search1.c_str(), newsize1);
aDataFound=aTree.SearchAhoCorasikMultiple( wcstring1 );
for (int iCount=0;
iCount<aDataFound.size();
++iCount)
printf(" AC Match Found : %S \n",aDataFound[iCount].sDataFound.c_str());
}
}
int main(int argc, char* argv[])
{
string pattern,text,line;
cout<<"Enter text file name.\n";
cin>>text;
cout<<"Enter patterns file name.\n";
cin>>pattern;
AC_search(text,pattern);
return 0;
}
</ctime></string></iostream></fstream></stdio.h></stdlib.h>