Cod sursa(job #2002982)

Utilizator Coroian_DavidCoroian David Coroian_David Data 21 iulie 2017 13:17:26
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <cstdio>

#include <cstring>

using namespace std;

FILE *f, *g;

int n, m;

char p[2000099];
char t[2000099];

void readFile()
{
    f = fopen("strmatch.in", "r");

    fgets(p, 2000099, f);
    fgets(t, 2000099, f);

    n = strlen(p);
    m = strlen(t);

    p[n --] = 0;
    t[m --] = 0;

    int i;
    for(i = n; i >= 1; i --)
        p[i] = p[i - 1];

    for(i = m; i >= 1; i --)
        t[i] = t[i - 1];

    fclose(f);
}

int urm[2000099];

void getUrm()
{
    urm[1] = 0;

    int k = 0;
    int i;
    for(i = 2; i <= n; i ++)
    {
        while(k > 0 && p[k + 1] != p[i])
            k = urm[k];

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

        urm[i] = k;
    }
}

int rez;

int rz[1009];

void getRez()
{
    int k = 0;
    int i;

    for(i = 1; i <= m; i ++)
    {

        while(k > 0 && p[k + 1] != t[i])
            k = urm[k];

        if(k + 1 < 0)
            printf("ERROE\n");

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

        if(k == n)
        {
            //k = urm[k];

            rez ++;

            ///1945626

          //  if(rez >= 137630)
         //       printf("%d ", i - n);

            if(rez <= 1000)
                rz[rez] = i - n + 1;
        }
    }
}

void solve()
{
    getUrm();

    getRez();
}

void printFile()
{
    g = fopen("strmatch.out", "w");

    fprintf(g, "%d\n", rez);

    int af;

    if(rez >= 1000)
        af = 1000;

    else
        af = rez;

    int i;
    for(i = 1; i <= af; i ++)
        fprintf(g, "%d ", rz[i]);

    fprintf(g, "\n");

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}