// QuickSearch.h

#ifndef QuickSearchh
#define QuickSearchh

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

// Quick and simple method of finding strings without needing them to be Null Terminated
// If you know the pattern length is going to be less than 256 characters, you could make the array one of BYTEs rather than DWORDs...

class CQuickSearch {
  DWORD TextLength;
  const char* Text;
  DWORD PatternLength;
  const char* Pattern;
  DWORD BCST[256]; // Quick Search Algorithm's bad-character shift table
  DWORD Resume;
public:
  CQuickSearch(const char* Text, const char* Pattern, DWORD textLength=0, DWORD patternLength=0) : Text(Text), Pattern(Pattern), TextLength(textLength ? textLength : strlen(Text)), PatternLength(patternLength ? patternLength : strlen(Pattern)), Resume(0) {
    for(DWORD i=0; i<   TextLength; ++i) BCST        [i] =PatternLength+1;
    for(DWORD i=TextLength; i< 256; ++i) BCST        [i] =1;
    for(DWORD i=0; i<PatternLength; ++i) BCST[Pattern[i]]=PatternLength-i;
  }
  virtual ~CQuickSearch() {}
  DWORD Find() {Resume=0; return FindNext();}
  DWORD FindNext() {
    for(DWORD i=Resume; i<=TextLength-PatternLength; i+=BCST[Text[i+PatternLength]]) {
      if(memcmp(Pattern, Text+i, PatternLength)==0) {
        Resume=i+BCST[Text[i+PatternLength]];
        return i;
    } }
    return (DWORD)-1;
  }
};

#ifdef Assert // Run tests if Tester.h is included in stdafx.h
namespace { // namespace prevents multiple definitions if instantiating in the header like this:
  struct QuickSearchTester : Tester {
    CBytes S;
    QuickSearchTester() {
      QuickSearchTest();
    }
    void QuickSearchTest() {
      CQuickSearch QS("GCATCGCAGAGAGTATACAGTAGCAGAGAGCG","GCAGAGAG");
      Assert(QS.FindNext()==5);
      Assert(QS.FindNext()==22);
      Assert(QS.FindNext()==-1);
      Assert(QS.Find()==5);
    }
  }_QuickSearchTester;
}
#endif // def Assert

#endif // ndef QuickSearchh