Cod sursa(job #1959906)

Utilizator mihai.alphamihai craciun mihai.alpha Data 10 aprilie 2017 00:38:45
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <stdio.h>
#include <string.h>

#define dim 2000000

char a[dim + 2], b[dim + 2];
int pi[dim + 1];
int sol[dim + 1];

FILE *fin, *fout;


int main()  {
    fin = fopen("strmatch.in", "r");
    fout = fopen("strmatch.out", "w");

    fgets(a, dim + 1, fin);
    fgets(b, dim + 1, fin);

    int m = strlen(a) - 2, n = strlen(b) - 2;
    int i, r = 0;
    for(i = 2;i <= m;i++)  {
        r = pi[i - 1];
        while(r && (a[r + 1] != a[i]))
            r = pi[r];
        if(a[r + 1] == a[i])
            r++;
        pi[i] = r;
    }

    r = 0;
    for(i = 1;i <= n;i++)  {
        while(r && (a[r + 1] != b[i]))
            r = pi[r];
        if(a[r + 1] == b[i])
            r++;
        if(r == m)
            sol[++sol[0]] = i - m;
    }

    fprintf(fout, "%d\n", sol[0]);
    for(i = 1;i <= (sol[0] <= 1000 ? sol[0] : 1000);i++)
        fprintf(fout, "%d ", sol[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}