Cod sursa(job #573090)

Utilizator miticaMitica mitica Data 5 aprilie 2011 21:26:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <cstring>
#include <algorithm>

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=0;

    urm[1]=0;
    for (i=2; i<=m; ++i)
    {
        while (k && 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+1,sizeof(A));
    f.getline(B+1,sizeof(B));
    A[0]=' ';
    B[0]=' ';
    m=strlen(A);
    n=strlen(B);
    n--;
    m--;

    make_prefix();

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

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

    return 0;
}