NotSoNaive.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/measure>
 
#include <alib/set>
#include <alib/vector>
 
#include <string/LinearString.h>
 
 
namespace stringology {
 
    namespace exact {
 
 
        class NotSoNaive{
        public:
            template < class SymbolType >
            static ext::set < unsigned > match ( const string::LinearString < SymbolType > & subject, const string::LinearString < SymbolType > & pattern );
 
        };
 
        template < class SymbolType >
        ext::set < unsigned > NotSoNaive::match ( const string::LinearString < SymbolType > & subject, const string::LinearString < SymbolType > & pattern ) {
            ext::set<unsigned> occ;
 
            measurements::start ( "Algorithm", measurements::Type::ALGORITHM );
            // if pattern is one char, skip the rest and use naive approach
            if (pattern.getContent().size() == 1) {
                for (unsigned i = 0; i < subject.getContent().size(); ++i) {
                    if (subject.getContent()[i] == pattern.getContent()[0]) occ.insert(i);
                }
                return occ;
            }
 
            if (pattern.getContent()[0] != pattern.getContent()[1]) {
                for (unsigned i = 0; i + pattern.getContent().size() <= subject.getContent().size(); ++i) {
                    bool match = true ;
                    // try to match the whole string, in case of mathing fist two characters you can schift by 2
                    for (unsigned j = 0; j < pattern.getContent().size(); ++j) {
                        if (subject.getContent()[i + j] != pattern.getContent()[j]) {
                            match = false ;
                            if (j > 1) {
                                ++i;
                                break;
                            } else break;
                        }
                    }
                    if ( match ) occ.insert(i);
                }
            } else {
                for (unsigned i = 0; i + pattern.getContent().size() <= subject.getContent().size(); ++i) {
                    bool match = true ;
                    // try to match the whole string, if pattern[0] matches and pattern[1] not, then advance by 2
                    for (unsigned j = 0; j < pattern.getContent().size(); ++j) {
                        if (subject.getContent()[i + j] != pattern.getContent()[j]) {
                            match = false ;
                            if (j == 1) {
                                ++i;
                                break;
                            } else break;
                        }
                    }
                    if ( match ) occ.insert(i);
                }
            }
            measurements::end() ;
            return occ;
 
        }
 
    } /* namespace exact */
 
} /* namespace stringology */