Cod sursa(job #2228769)

Utilizator VladAdrianaVlad Adriana VladAdriana Data 4 august 2018 18:10:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <algorithm>
#include <cstring>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int nr;
char a[2000005],b[2000005];
int t[2000005], ap[1005];

int main()
{
    int lgA, lgB;
    fin.getline(a,2000005);
    fin.getline(b,2000005);
    lgA = strlen(a);
    lgB = strlen(b);

    t[0]=-1;
    for(int prec=0, act=1; act <= lgA; ++act, ++prec)
    {
        if(a[prec] == a[act])
        {
            t[act] = t[prec];

        }
        else
        {
            t[act] = prec;
            do
            {
                prec=t[prec];
            }
            while(prec >= 0 && a[prec] != a[act]);

        }
    }

    for(int i=0, j=0; i<lgB; )
    {
        if(a[j]==b[i])
        {
            i++;
            j++;
            if(j==lgA)
            {
                nr++;
                if(nr<=1000) ap[nr]=i-lgA;
            }
        }
        else
        {
            j=t[j];
            if(j==-1)
            {
                ++i;
                j=0;
            }
        }
    }

    fout<<nr<<'\n';
    for(int i=1;i<=min(nr,1000);i++)
    {
        fout<<ap[i]<<' ';
    }
    return 0;
}