Cod sursa(job #2516126)

Utilizator marinaoprOprea Marina marinaopr Data 30 decembrie 2019 13:46:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <stdio.h>
#include <string.h>
#include <iostream>

#define LG 2000005

using namespace std;

FILE *fin = fopen("strmatch.in", "r");
FILE *fout = fopen("strmatch.out", "w");

char patt[LG],txt[LG];
int p,t,i,lg,lps[LG],ap[1005],nrap;

int main()
{
    fgets(patt+1, LG-2, fin);
    fgets(txt+1, LG-2, fin);
    patt[0] = txt[0] = '.';
    p = strlen(patt)-2;
    t = strlen(txt)-2;

    for(i=2; i<=p; ++i)
    {
        while(patt[i] != patt[lg+1] and lg>0)
            lg = lps[lg];
        if(patt[i] == patt[lg+1])
            lg++;
        lps[i] = lg;
    }

    lg = 0;
    for(i=1; i<=t; ++i)
    {
        while(txt[i] != patt[lg+1] and lg>0)
            lg = lps[lg];

        if(txt[i] == patt[lg+1])
            ++lg;

        if(lg == p)
        {
            ++nrap;
            if(nrap <= 1000)
                ap[nrap] = i-p;
            lg = lps[lg];
        }
    }

    fprintf(fout, "%d\n", nrap);
    nrap = min(nrap, 1000);
    for(i=1; i<=nrap; ++i)
        fprintf(fout, "%d ", ap[i]);

    fclose(fin);
    fclose(fout);
    return 0;
}