HammingBitParalelism.h

Go to the documentation of this file.

 
#pragma once
 
#include <exception>
#include <string/LinearString.h>
 
#include "BitParalelism.h"
 
namespace stringology {
 
namespace simulations {
 
class HammingBitParalelism {
public:
    template <class SymbolType>
    static ext::set<unsigned int> search(const string::LinearString<SymbolType> & text, const string::LinearString<SymbolType> & pattern, unsigned int errors);
};
 
 
template <class SymbolType>
ext::set<unsigned int> HammingBitParalelism::search(const string::LinearString<SymbolType> & text, const string::LinearString<SymbolType> & pattern, unsigned int errors) {
  // 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;
 
  ext::vector<ext::vector<bool> > B_vectors;
  for(unsigned int i=0; i<=errors; i++) {
    B_vectors.push_back(ext::vector<bool>(pattern.getContent().size(), 1));
  }
 
  for(unsigned int i=0; i<text.getContent().size(); i++) {
    ext::vector< ext::vector<bool> > previous_B_vectors = B_vectors;
 
    B_vectors[0] = (B_vectors[0] << 1) | D_vectors[text.getContent()[i]];
 
    for(unsigned int j=1; j<=errors; j++) {
      B_vectors[j] = ( (B_vectors[j] << 1) | D_vectors[text.getContent()[i]] ) & (previous_B_vectors[j-1] << 1);
    }
 
    for(const auto & B_vector : B_vectors) {
      if ( ! B_vector [ pattern.getContent ( ).size ( ) - 1 ] ) {
        result.insert(i + 1);
        break;
      }
    }
  }
 
  return result;
}
 
} // namespace simulations
 
} // namespace stringology