Cod sursa(job #1533102)

Utilizator herbertoHerbert Mohanu herberto Data 22 noiembrie 2015 00:59:12
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 1.03 kb
#include <stdio.h>
#include <stdlib.h>

#define MAXN 2000000

char v1[MAXN], v2[MAXN];
int x[MAXN], ret[1001];
int main(){
  FILE*fin=fopen("strmatch.in", "r");
  FILE*fout=fopen("strmatch.out", "w");
  int n, i, k, c, m, nr, q, kmp, j;
  c=fgetc(fin);
  n=0;
  while(c!='\n'){
    n++;
    v1[n]=c;
    c=fgetc(fin);
  }
  c=fgetc(fin);
  m=0;
  while(c!='\n' && c!=EOF){
    m++;
    v2[m]=c;
    c=fgetc(fin);
  }
  x[1]=0;
  for(i=2; i<=n; i++){
    if(v1[i]==v1[x[i-1]+1])
      x[i]=x[i-1]+1;
    else{
      j=i-1;
      while(j>1 && v1[x[j]+1]!=v1[i])
        j=x[j];
      x[i]=x[j]+1;
      if((j==0 || j==1) && v1[1]!=v1[i])
        x[i]=0;
    }
  }
  kmp=nr=0;
  for(i=1;i<=m;i++){
    while(v2[i]!=v1[kmp+1] && kmp!=0)
      kmp=x[kmp];
    if(v2[i]==v1[kmp+1])
      kmp++;
    if(kmp==n){
      nr++;
      if(nr<1000)
        ret[nr]=i-kmp;
    }
  }
  fprintf(fout, "%d\n", nr);
  if(nr>1000)
    nr=1000;
  for(i=1; i<=nr; i++)
    fprintf(fout, "%d ", ret[i]);
  return 0;
}