The well-known Knuth-Morris-Pratt algorithm.

This algorithm can be explained in terms of the sequence matching between input and patterns this way:

void KMP(string pattern, string text, vector<int> *positions) {

    int patternLength = pattern.length();

    int textLength = text.length();

    int* next =  PreProcess(pattern);

 if (next == 0) return;

    int i = 0;

    int j = 0;

    while ( j < textLength )

 {

  while(true)

   if (text[j] == pattern[i]) //matches

   {

    i++;   // yes, move on to the next state

    if (i == patternLength)  // maybe that was the last state

    {

     // found a match;

     positions->push_back(j-(i-1));

     i = next[i];

    }

    break;

   }

   else if (i == 0) break; // no match in state j = 0, give up

   else i = next[i];

  j++;

 }

}

int* PreProcess( string pattern) {

 int patternLength = pattern.length();

 if (patternLength == 0) return 0;

    int * next = new int[patternLength + 1];

    if (next == 0) return 0;

    next[0] = -1;  // set up for loop below; unused by KMP

    int i = 0;

    int j = -1;

    // next[0] = -1;

    // int len = pattern.length();

    while (i < patternLength) {

  next[i + 1] = next[i] + 1;

  while ( next[i+1] > 0 &&

    pattern[i] != pattern[next[i + 1] - 1])

   next[i + 1] = next[next[i + 1] - 1] + 1;

  i++;

 }

    return next;

}

Usage: DroneDataAddition.docx