КМП

// Реализация алгоритма КМП, отсюда: http://ru.wikibooks.org/wiki/%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0_%D0%9A%D0%BD%D1%83%D1%82%D0%B0_%E2%80%94_%D0%9C%D0%BE%D1%80%D1%80%D0%B8%D1%81%D0%B0_%E2%80%94_%D0%9F%D1%80%D0%B0%D1%82%D1%82%D0%B0

# include <string>
# include <vector>

using namespace std;

string::size_type KMP(const string& S, int begin, const string& pattern){
        vector<int> pf (pattern.length());

        pf[0] = 0;
        for (int k = 0, i = 1; i<pattern.length(); ++i){
                while(k>0 && pattern[i] != pattern[k])
                        k = pf[k-1];

                if (pattern[i] == pattern[k])
                        k++;

                pf[i] = k;
        }

        for (int k = 0, i = begin; i<S.length(); ++i){
                while ((k>0) && (pattern[k] != S[i]))
                        k = pf[k-1];

                if (pattern[k] == S[i])
                        k++;

                if (k==pattern.length())
                        return (i-pattern.length()+1);//либо продолжаем поиск следующих вхождений
        }

        return (string::npos);
}