Cod sursa(job #2002976)

Utilizator Coroian_DavidCoroian David Coroian_David Data 21 iulie 2017 12:49:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <cstdio>

#include <cstring>

using namespace std;

FILE *f, *g;

int n, m;

char p[2000009];
char t[2000009];

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

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

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

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

    fclose(f);
}

int urm[2000009];

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

    int k = -1;
    int i;
    for(i = 1; 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[2000009];

void getRez()
{
    int k = -1;
    int i;

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

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

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

void solve()
{
    getUrm();

    getRez();
}

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

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

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

    fprintf(g, "\n");

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}