Cod sursa(job #572897)

Utilizator miticaMitica mitica Data 5 aprilie 2011 18:40:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <cstring>

using namespace std;

const int nmax = 2000005;

char A[nmax],B[nmax];
int i,urm[nmax],k,n,m,v[1005],q;

void make_prefix()
{
    int i,k=-1;

    urm[0]=0;
    for (i=1;i<m;++i)
    {
        while (k>0 && A[k+1]!=A[i])
            k=urm[k];
        if (A[k+1]==A[i])
            k++;
        urm[i]=k;
    }
}

int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");

    f.getline(A,sizeof(A));
    f.getline(B,sizeof(B));
    m=strlen(A);
    n=strlen(B);

    make_prefix();

    k=-1;
    for (i=0;i<n;++i)
    {
        while (k>0 && A[k+1]!=B[i])
            k=urm[k];
        if (A[k+1]==B[i])
            k++;
        if (k==m-1)
        {
            k=urm[m-1];
            q++;
            if (q<=1000)
                v[q]=i-m+1;
        }
    }

    g<<q<<'\n';
    for (i=1;i<=min(q,1000);++i)
        g<<v[i]<<' ';

    return 0;
}