Cod sursa(job #1528473)

Utilizator Alex.PAlexandru Pacurar Alex.P Data 19 noiembrie 2015 19:05:05
Problema Potrivirea sirurilor Scor 20
Compilator c Status done
Runda Arhiva educationala Marime 1.21 kb
#include <stdio.h>
#include <stdlib.h>

int prefix[2000001];
int prefix2[2000001];
char v1[2000001];
char v2[2000001];
int poz[2000000];

int main()
{
    FILE *fin, *fout;
    fin=fopen("strmatch.in","r");
    fout=fopen("strmatch.out","w");
    int n,l1,l2,i,kmp,gasit;
    char c;
    c=fgetc(fin);
    i=1;
    while(c!=' ' && c!='\n'){
      v1[i]=c;
      i++;
      c=fgetc(fin);
    }
    l1=i;
    while(c==' ' || c=='\n')
      c=fgetc(fin);
    i=1;
    while(c!=' ' && c!='\n' && c!=EOF){
      v2[i]=c;
      i++;
      c=fgetc(fin);
    }
    l2=i;
    for(n=2;n<l1;n++){
      i=n;
      while(v1[n]!=v1[prefix[i-1]+1] && i>1)
        i=prefix[i-1]+1;
      prefix[n]=prefix[i-1]+1;
      if(i==1 && v1[n]!=v1[i])
          prefix[n]=0;
    }
    kmp=1;
    gasit=0;
    for(n=1;n<l2;n++){
      while(v2[n]!=v1[kmp] && kmp>1)
        kmp=prefix2[kmp-1];
      prefix2[n]=kmp;
      if(kmp==1 && v2[n]!=v1[1])
        prefix2[n]=0;
      else
        kmp++;
      if(prefix2[n]==l1-1){
        poz[gasit]=n-l1+1;
        gasit++;
      }
    }
    fprintf(fout,"%d\n",gasit);
    for(i=0;i<gasit;i++){
      fprintf(fout,"%d ",poz[i]);
    }
    return 0;
}