Cod sursa(job #2480811)

Utilizator ana.pintiliciucAna Maria Pintiliciuc ana.pintiliciuc Data 26 octombrie 2019 10:31:04
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#define NMAX 2000005
#include <cstring>

using namespace std;

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

char a[NMAX], b[NMAX];
int p[NMAX];
int n, m, nr, poz[1005];

void generareprefixe()
{
    p[1]=0;
    int k=0; ///indicele potrivirii
    for(int i=2;i<=n;i++)
    {
        while(k!=0 && a[i]!=a[k+1])
            k=p[k];

        if(a[i]==a[k+1])
            ++k;
        p[i]=k;
    }
}

void matching()
{
    int k=0;
    for(int i=2;i<=m;i++)
    {
        while(k!=0 && b[i]!=a[k+1])
            k=p[k];

        if(b[i]==a[k+1])
            ++k;

        if(k==n)
        {
            nr++;
            if(nr<1000)
                poz[nr]=i-n;
        }
    }
}

int main()
{
    f.getline(a+1, NMAX);
    f.getline(b+1, NMAX);
    ///g<<a+1<<'\n'<<b+1;
    n=strlen(a+1);
    m=strlen(b+1);
    generareprefixe();
    matching();
    g<<nr<<'\n';
    for(int i=1;i<=nr;i++)
        g<<poz[i]<<' ';

    return 0;
}