Cod sursa(job #1649254)

Utilizator DiClauDan Claudiu DiClau Data 11 martie 2016 13:00:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include<stdio.h>
using namespace std;
const int N = 2000005;
char a[N], b[N];
int pi[N], sol[N];
int na = 0, nb = 0, nrsol;
void precalc ()
{
    int k = 0;
    pi[0] = 0;
    int q;
    for (q = 1; q < na; q++)
    {
        while ((k != 0) && a[k] != a[q])
            k = pi[k - 1];
        if (a[k] == a[q])
            k++;
        pi[q] = k;
    }
}
void gaseste ()
{
    int q = 0, i;
    for (i = 0; i < nb; i++)
    {
        while ((q != 0) && a[q] != b[i])
            q = pi[q - 1];
        if (a[q] == b[i])
            q++;
        if (q == na)
            sol[++nrsol] = i - na + 1;
    }
}
int main ()
{
    FILE *in, *out;
    in = fopen ("strmatch.in", "r");
    out = fopen ("strmatch.out", "w");
    char x;
    x = getc (in);
    while (x != '\n')
    {
        a[na++] = x;
        x = fgetc (in);
    }
    x = fgetc (in);
    while (x != EOF && x != '\n')
    {
        b[nb++] = x;
        x = fgetc (in);
    }
    precalc();
    gaseste();
    fprintf (out, "%d\n", nrsol);
    int i;
    if (nrsol > 1000)
        nrsol = 1000;
    for (i = 1; i <= nrsol; i++)
        fprintf (out, "%d ", sol[i]);
    return 0;
}