ExactBitParalelism.h

Go to the documentation of this file.

 
#pragma once
 
#include <exception>
#include <string/LinearString.h>
 
#include "BitParalelism.h"
 
namespace stringology {
 
namespace simulations {
 
class ExactBitParalelism {
public:
    template <class SymbolType>
    static ext::set<unsigned int> search(const string::LinearString<SymbolType> & text, const string::LinearString<SymbolType> & pattern);
};
 
 
template <class SymbolType>
ext::set<unsigned int> ExactBitParalelism::search(const string::LinearString<SymbolType> & text, const string::LinearString<SymbolType> & pattern) {
 
  // preparation stage
  ext::set<SymbolType> common_alphabet = text.getAlphabet();
  common_alphabet.insert(pattern.getAlphabet().begin(), pattern.getAlphabet().end());
 
  ext::map<SymbolType, ext::vector<bool> > D_vectors = BitParalelism::constructDVectors(common_alphabet, pattern);
 
  // computation part
  ext::set<unsigned int> result;
 
  auto B_vector = ext::vector<bool>(pattern.getContent().size(), 1);
 
  for(unsigned int i = 0; i<text.getContent().size(); i++) {
    B_vector = (B_vector << 1) | D_vectors[text.getContent()[i]];
 
    if ( ! B_vector [ pattern.getContent ( ).size ( ) - 1 ] ) {
        result.insert(i + 1);
    }
  }
 
  return result;
}
 
} // namespace simulations
 
} // namespace stringology