Cod sursa(job #1456604)

Utilizator cella.florescuCella Florescu cella.florescu Data 1 iulie 2015 13:12:07
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXPOS 1000
char a[2000002], b[2000002];
int pi[2000001], pos[MAXPOS];
int main()
{
    FILE *fin, *fout;
    int n, m, k, p, i;
    fin=fopen("strmatch.in", "r");
    fgets(a+1, 2000010, fin);
    n=strlen(a+1);
    fgets(b+1, 2000010, fin);
    m=strlen(b+1);
    fclose(fin);
    --n; --m;
    k=0;
    for(i=2; i<=n; i++){
      while(k && a[k+1]!=a[i])
        k=pi[k];
      if(a[k+1]==a[i])
        ++k;
      pi[i]=k;
    }
    p=k=0;
    fout=fopen("strmatch.out", "w");
    for(i=1; i<=m; i++){
      while(k && a[k+1]!=b[i])
        k=pi[k];
      if(a[k+1]==b[i])
        ++k;
      if(k==n){
        if(p<MAXPOS)
          pos[p]=i-n;
        ++p;
      }
    }
    fprintf(fout, "%d\n", p);
    p=p<=1000?p:1000;
    for(i=0; i<p; i++)
      fprintf(fout, "%d ", pos[i]);
    fprintf(fout, "\n");
    fclose(fout);
    return 0;
}