Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Автор: Климчук Аня.
- // Описание: Поиск позиций вхождения шаблона в строке с помощью алгоритма Ахо-Корасика.
- #include <iostream>
- #include <vector>
- #include <string>
- #include <map>
- using namespace std;
- // Вершина Бора.
- class CVertex{
- public:
- CVertex( int parent_ = -1, char symbol_ = '#' ){
- parent = parent_;
- symbol = symbol_;
- isTerminal = false;
- suffLink = -1;
- up = -1;
- };
- void AddSon( char symbol, int son ) {
- sons[symbol] = son;
- };
- int GetSon( char symbol ) const{
- map< char, int >::const_iterator it = sons.find( symbol );
- if( it != sons.end() )
- return it->second;
- return -1;
- }
- void AddGoLink( char symbol, int vertex ) {
- go[symbol] = vertex;
- }
- int GetGoLink( char symbol ) const{
- map< char, int >::const_iterator it = go.find( symbol );
- if( it != go.end() )
- return it->second;
- return -1;
- }
- int CountNeighbor() const{
- return sons.size();
- }
- void BeTerminal() {
- isTerminal = true;
- }
- bool IsTerminal() const{
- return isTerminal;
- }
- void AddPattern( int number ) {
- PatternNumbers.push_back( number );
- }
- void AddSuffLink( int suffLink_ ) {
- suffLink = suffLink_;
- }
- int GetSuffLink() const{
- return suffLink;
- }
- int GetParent() const{
- return parent;
- }
- char GetSymbol() const{
- return symbol;
- }
- void AddUp( int up_ ) {
- up = up_;
- }
- int GetUp() const{
- return up;
- }
- int CountPattern() const{
- return PatternNumbers.size();
- }
- int GetPattern( int i ) const{
- return PatternNumbers[i];
- }
- private:
- // Родитель, т.е. вершина, из которой пришли в данную.
- int parent;
- // Символ, по которому пришли в данную вершину.
- char symbol;
- // Индикатор, является ли данная вершина terminal.
- bool isTerminal;
- // Номера шаблонов, для которых данная вершина является terminal.
- vector<int> PatternNumbers;
- // map сыновей
- map< char, int > sons;
- // map переходов.
- map< char, int > go;
- // суффиксная ссылка
- int suffLink;
- // сжатая суффиксная ссылка
- int up;
- };
- // Бор.
- class CBor{
- public:
- CBor() {
- allVertex.push_back( CVertex() );
- root = allVertex.size() - 1;
- }
- void AddPattern( string & patt )
- {
- patterns.push_back( patt );
- int current = root;
- for( int i = 0; i < patt.length(); ++i ) {
- int son = allVertex[current].GetSon( patt[i] );
- if( son != -1 ) {
- current = son;
- } else {
- allVertex.push_back( CVertex( current, patt[i] ) );
- int new_vertex = allVertex.size() - 1;
- allVertex[current].AddSon( patt[i], new_vertex );
- current = new_vertex;
- }
- }
- allVertex[current].BeTerminal();
- allVertex[current].AddPattern( patterns.size() - 1 );
- }
- // Суффиксная ссылка.
- // Возвращает вершину, в которой заканчивается максимальный несобственный суффикс.
- int GetSuffLink( int v );
- // Переход из вершины по символу.
- int GetLink( int v, char symbol );
- // Сжатая суффиксная ссылка.
- int GetUp( int v );
- int GetRoot() {
- return root;
- }
- int GetPatternSize( int i ) const{
- return patterns[i].size();
- }
- string GetPattern( int i ) const{
- return patterns[i];
- }
- void Check( int v, int i );
- void Find( string & text);
- private:
- int root;
- vector< CVertex > allVertex;
- vector< string > patterns;
- };
- int CBor::GetSuffLink( int v )
- {
- CVertex * vertex = &allVertex[v];
- // Если на данный момент нет suffLink.
- if( vertex->GetSuffLink() == -1 ) {
- if( v == root || vertex->GetParent() == root ) {
- vertex->AddSuffLink( root );
- } else {
- vertex->AddSuffLink( GetLink( GetSuffLink( vertex->GetParent() ), vertex->GetSymbol()) );
- }
- }
- return vertex->GetSuffLink();
- }
- int CBor::GetLink( int v, char symbol ) {
- CVertex * vertex = &allVertex[v];
- int link = vertex->GetGoLink( symbol );
- // Если из данной вершины уже есть переход по этому символу.
- if( link != -1 ) {
- return link;
- }
- link = vertex->GetSon( symbol);
- // Если у вершины есть ребенок с переходом по этому символу.
- if( link != -1 ) {
- vertex->AddGoLink( symbol, link );
- return link;
- }
- // Если данная вершина корень.
- if ( v == root) {
- vertex->AddGoLink( symbol, root );
- return root;
- }
- link = GetLink( GetSuffLink( v ), symbol );
- vertex->AddGoLink( symbol, link );
- return link;
- }
- int CBor::GetUp( int v ) {
- CVertex * vertex = &allVertex[v];
- int link = vertex->GetUp();
- if( link != -1 ) {
- return link;
- }
- link = GetSuffLink( v );
- if( allVertex[link].IsTerminal() || link == root) {
- vertex->AddUp( link );
- return link;
- }
- link = GetUp( GetSuffLink( v ) );
- vertex->AddUp( link );
- return link;
- }
- void CBor::Check( int v, int i ) {
- for( int u = v; u != 0; u = GetUp( u ) ) {
- CVertex * vertex = &allVertex[u];
- if( vertex->IsTerminal() ) {
- for( int j = 0; j < vertex->CountPattern(); ++j ) {
- cout << i - GetPatternSize( vertex->GetPattern( j ) ) + 1 << " ";
- cout << GetPattern( vertex->GetPattern( j ) ) << endl;
- }
- }
- }
- }
- void CBor::Find( string & text ) {
- int current = GetRoot();
- for( int i = 0; i < text.length(); ++i ) {
- current = GetLink( current, text[i] );
- Check( current, i + 1 );
- }
- }
- int main()
- {
- CBor b;
- /*string s = "he";
- b.AddPattern( s );
- s = "she";
- b.AddPattern( s );
- s = "his";
- b.AddPattern( s );
- s = "hers";
- b.AddPattern( s );
- */
- string s = "abc";
- b.AddPattern( s );
- s = "bcdc";
- b.AddPattern( s );
- s = "bcdc";
- b.AddPattern( s );
- s = "cccb";
- b.AddPattern( s );
- s = "bcdd";
- b.AddPattern( s );
- s = "bbbc";
- b.AddPattern( s );
- s = "abcdcbcddbbbcccbbbcccbb";
- b.Find( s );
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement