Cod sursa(job #932169)

Utilizator Bogdan13Bogdan Stoian Bogdan13 Data 28 martie 2013 19:00:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<fstream>
#include<cstring>
#define LMAX 2000005
using namespace std;

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

char S[LMAX],P[LMAX];
int pi[LMAX],lens,lenp,nr,afis[1005];

void prefix()
{
    int q=0;

    for (int i=2;i<=lenp;i++)
    {
        while(q&&P[q+1]!=P[i]) q=pi[q];

        if (P[q+1]==P[i]) q++;

        pi[i]=q;
    }
}


int main()
{
    f.getline(P+1,LMAX,'\n');
    f.getline(S+1,LMAX,'\n');
    S[0]=' ';
    P[0]=' ';
    lens=strlen(S)-1;
    lenp=strlen(P)-1;

    prefix();
int    q=0;
    for (int i=1;i<=lens;i++)
    {
        while (q&&P[q+1]!=S[i]) q=pi[q];

        if (P[q+1]==S[i]) q++;

        if (q==lenp)
        {
            q=pi[lenp];
            nr++;
            if (nr<=1000)
            afis[nr]=i-lenp;

        }

    }

    g<<nr<<'\n';
    for (int i=1;i<=nr&&i<=1000;i++)
    g<<afis[i]<<" ";

return 0;
}