Cod sursa(job #1412244)

Utilizator rares96cheseliRares Cheseli rares96cheseli Data 1 aprilie 2015 10:49:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

int N, M, pi[2000005], K, dim, sol[2000005];
char a[2000005], b[2000005];

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

int main()
{
    f>>(a+1)>>(b+1);
    N=strlen(a+1); M=strlen(b+1);
    bagapi(); K=0;

    for (int i=1; i<=M; ++i)
    {
        while (K>0 && a[K+1]!=b[i]) K=pi[K];
        if (a[K+1]==b[i]) ++K;
        if (K==N)
            sol[++dim]=i-N, K=pi[N];
    }

    g<<dim<<'\n'; dim=min(dim, 1000);
    for (int i=1; i<=dim; ++i)
        g<<sol[i]<<' ';
    return 0;
}