Cod sursa(job #1478552)

Utilizator ConsstantinTabacu Raul Consstantin Data 28 august 2015 22:48:17
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <cstdio>
#include <cstring>

#define IN_FILE_NAME "strmatch.in"
#define OUT_FILE_NAME "strmatch.out"
#define NMAX 2000001
FILE *in, *out;
char A[NMAX], B[NMAX];
int pos[NMAX], rez[NMAX], count;

void read() {
  fscanf(in, "%s\n", A);
  fscanf(in, "%s\n", B);
  printf("%s\n%s\n",A,B);
}

void process(char A[]) {
  int len = strlen(A);
  int match = 0;
  int i;
  for (i = 1 ; i < len ; i++) {
    if(A[match] == A[i]) {
      match ++ ;
      pos[i] = match;
    } else {
      match = 0;
    }
  }
  printf("EndProcess\n");
}

void match(char A[], char B[]) {
  int lenA, lenB;
  lenA = strlen(A);
  lenB = strlen(B);
  int match = 0 ;
  printf("start match\n");
  for (int i = 0 ; i < lenB ; i++) {
    printf("%c %c\n", B[i], A[match]);

    if(B[i] == A[match]) {
      match++;
      if (match == lenA && count < 1000) {
        rez[count++] = i  - match + 1;
        match = pos[match-1];
      }
    } else {
      match=0;
      while(match && B[i] != A[match]) {
        match = pos[match-1];
      }
    }
  }
}

void solve() {
  process(A);
  match(A,B);
}

void printResults(){
  fprintf(out, "%d\n", count);
  for(int i = 0 ; i < count; i++) {
    fprintf(out, "%d ", rez[i]);
  }
}

int main() {
  in = fopen(IN_FILE_NAME, "r");
  out = fopen(OUT_FILE_NAME, "w");
  read();
  solve();
  printResults();
  fclose(in);
  fclose(out);
  return 0;
}