GalilSeiferas.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/measure>
 
#include <alib/set>
#include <alib/vector>
 
#include <string/LinearString.h>
#include <algorithm>
#include <common/createUnique.hpp>
#include <alphabet/EndSymbol.h>
 
 
namespace stringology {
 
    namespace exact {
 
 
        class GalilSeiferas{
        public:
            template < class SymbolType >
            static ext::set < unsigned > match ( const string::LinearString < SymbolType > & subject, const string::LinearString < SymbolType > & pattern );
 
        };
 
        size_t div_up (const size_t &x ,const size_t  &y ) {
            return ( x % y == 1 ) ? x / y + 1 : x / y ;
        }
 
        template < class SymbolType >
        ext::set < unsigned > GalilSeiferas::match ( const string::LinearString < SymbolType > & subject, const string::LinearString < SymbolType > & pattern ) {
            ext::set<unsigned> occ;
 
            // add terminating symbol to text
            SymbolType endSymbol = common::createUnique ( alphabet::EndSymbol::instance < SymbolType > ( ), subject.getAlphabet ( ) );
            ext::vector < SymbolType > content = subject.getContent ( );
            content.push_back ( endSymbol );
 
            // add terminating symbol to pattern
            SymbolType endSymbol2 = common::createUnique ( alphabet::EndSymbol::instance < SymbolType > ( ), pattern.getAlphabet ( ) );
            ext::vector < SymbolType > contentPatt = pattern.getContent ( );
            contentPatt.push_back ( endSymbol );
 
            std::vector y = content ;
            std::vector x = contentPatt ;
            size_t n = y.size() - 1 , m = x.size() - 1 ;
 
            unsigned k = 4 ;
            size_t p = 0 , q = 0 ;
            size_t s = 0 , p1 = 1 , q1 = 0 ;
            size_t p2 = 0 , q2 = 0 ;
 
 
            measurements::start ( "Algorithm", measurements::Type::ALGORITHM );
            newp1:
            while( x[s + p1 + q1] == x[s + q1] ) ++ q1 ;
            if ( p1 + q1 >= k * p1 ) {
                p2 = q1 ;
                q2 = 0 ;
                goto newp2 ;
            }
 
 
            if ( s + p1 + q1 == m ) goto search ;
            p1 += std::max( static_cast < size_t > ( 1 ) , div_up ( q1 , k )  ) ;
            q1 = 0 ;
            goto  newp1 ;
 
            newp2:
            while( x[s + p2 + q2] == x[s + q2] && p2 + q2 < k* p2 ) ++ q2 ;
            if ( p2 + q2 == k * p2 ) goto parse ;
            if ( s + p2 + q2 == m ) goto search ;
            if ( q2 == p1 + q1 ) {
                p2 += p1 ;
                q2 -= p1 ;
            } else {
                p2 += std::max ( static_cast < size_t > ( 1 ) , div_up(q2 , k)) ;
                q2 = 0 ;
            }
            goto newp2 ;
 
            parse:
            while ( x[s + p1 + q1] == x[s + q1]) ++ q1 ;
            while ( p1 + q1 >= k * p1 ) {
                s += p1 ;
                q1 -= p1 ;
            }
            p1 += std::max ( static_cast < size_t > ( 1 ) , div_up(q1 , k ));
            q1 = 0 ;
            if ( p1 < p2 ) goto parse ;
            else goto newp1 ;
 
            search:
            while ( p <= n - m ) {
                while ( p + s + q < n && y[p + s + q] == x[s + q]) ++q;
                if (q == m - s && std::equal( y.begin() + p, y.begin() + p + s , x.begin())) occ.insert(p);
                if (q == p1 + q1) {
                    p += p1;
                    q -= p1;
                } else {
                    p += std::max ( static_cast < size_t > ( 1 ), div_up(q, k));
                    q = 0;
                }
            }
            measurements::end() ;
            return occ ;
        }
 
 
    } /* namespace exact */
 
} /* namespace stringology */