Cod sursa(job #1053218)

Utilizator rares96cheseliRares Cheseli rares96cheseli Data 12 decembrie 2013 15:36:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <cstring>
#include <fstream>
#include <algorithm>
#define MAXN 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

char X[MAXN], Y[MAXN];
int Pi[MAXN], d[MAXN], K, N, M, pos[1024], n=0;

void constructie_pi()
{
    K=0; Pi[1]=0;
    for (int i=2; i<=M; ++i)
    {
        while ( K && X[i]!=X[K+1] ) K=Pi[K];
        if ( X[i]==X[K+1] ) K++;
                Pi[i]=K;
    }
}

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

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