Cod sursa(job #1138481)

Utilizator rares96cheseliRares Cheseli rares96cheseli Data 10 martie 2014 09:18:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

int N, M, nrap, pi[2000005], k, pos[1024];
char X[2000005], Y[2000005];

void biuld_pi()
{
    for (int i=2; i<=N; ++i)
    {
        while (k>0 && X[k+1]!=X[i])
            k=pi[k];
        if (X[k+1]==X[i]) ++k;
        pi[i]=k;
    }
}

int main()
{
    f>>(X+1); f>>(Y+1);
    N=strlen(X+1); M=strlen(Y+1);

    biuld_pi(); k=0;
    for (int i=1; i<=M; ++i)
    {
        while (k>0 && X[k+1]!=Y[i])
            k=pi[k];
        if (X[k+1]==Y[i]) ++k;
        if (k==N)
        {
            ++nrap;
            if (nrap<=1000) pos[nrap]=i-N;
        }
    }
    pos[0]=min(nrap, 1000); g<<nrap<<'\n';
    for (int i=1; i<=pos[0]; ++i)
        g<<pos[i]<<' ';
    return 0;
}