String searching in linear time, O(n).

kmp.cpp

#include <iostream>
#include <thread>
#include <string>
#include <vector>
using namespace std;

// This KMP algorithm is described, explained and written out at 
// http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm
void preprocess( string pattern, vector<int> &b ){
    int m = pattern.length();
    int i = 0, j = -1;

    b[i] = j;
    while(i < m){
        while( (j >= 0) && (pattern[i] != pattern[j]) ) j = b[j];
        i++; j++;
        b[i] = j;
    }
}

void search(const string x, const string pattern, const vector<int> b){
    int n = x.length();
    int m = pattern.length();
    int i = 0, j = 0;
    while( i < n ) {
        while ( (j >= 0) && (x[i] != pattern[j]) ) j = b[j];
        i++; j++;
        if (j == m){
            cout << (i-j) << " ";
            j = b[j];
        }
    }
}

int main(){
    string x = "dsdsdsds";
    string pattern = "s";
    cout << "string: " << x << endl;
    cout << "search for: " << pattern << endl;
    cout << "found at ";
    vector<int> b( pattern.length()+1 );

    preprocess( pattern, b );
    search( x, pattern, b );

    cin.get();
}