kmp.cpp

#include <iostream>
#include <algorithm>

using namespace std;

void kmp(string siano, string igla)
{
    int P[igla.size()], t = 0, j = 0, i = 1;
    P[0]=0; P[1]=0;

    for (int j = 2; j <= igla.size(); j++)
    {
        while ((t>0) && (igla[t] != igla[j-1]))
        {
            t = P[t];
            t++;
        }

        P[j-1] = igla[t]==igla[j-1]?t:P[t];
    }

    while (i <= siano.size()-igla.size()+1)
    {
        for (j = P[j]; (j<igla.size()) && (igla[j] == siano[i+j-1]); j++);

        if (j == igla.size())
            cout << i << ' ';

        i += 1>j-P[j]? // Just,
             1:j-P[j]; // Smile
   }
}

int main()
{
    string siano, igla;

    srand(time(0));

    for (int i = 0; i < 100000; i++)
        siano += rand()%2?"1":"0"; // Smile
    for (int i = 0; i < 10; i++)
        igla += rand()%2?"1":"0"; // Smile

    kmp(siano, igla);

    return EXIT_SUCCESS;
}