Cod sursa(job #2218842)

Utilizator petrooPetru G petroo Data 5 iulie 2018 23:47:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <stdio.h>
#include <string.h>

#define SIZE 2000000

char A[SIZE], B[SIZE];
int prefix[SIZE];
int sol[SIZE];
int matches;

void build_prefix() {

  int length = strlen(A);
  int index = 0;
  for(int i = 1; i < length;) {

    if (A[index] == A[i]) {
      index += 1;
      prefix[i] = index;
      i += 1;
    }
    else {
      if (index != 0)
        index = prefix[index - 1];
      else {
        prefix[i] = 0;
        i += 1;
      }
    }
  }
}

void KMP() {

  int pattern_index = 0;
  int text_index = 0;
  int pattern_size = strlen(A);
  int text_size = strlen(B);
  pattern_index = text_index = 0;
  while (text_index < text_size) {

    if (B[text_index] == A[pattern_index]) {
      text_index++;
      pattern_index++;
      if (pattern_index == pattern_size) {
        pattern_index = prefix[pattern_size - 1];
        sol[matches] = text_index - pattern_size;
        matches += 1;
      }
    } else {
      if (pattern_index != 0)
        pattern_index = prefix[pattern_index - 1];
      else {
        text_index++;
      }
    }
  }

}


int main(void) {

  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);

  scanf("%s", A);
  scanf("%s", B);


  build_prefix();
  KMP();

  printf("%d\n", matches);
  if (matches > 1000)
    matches = 1000;
  for (int i = 0; i < matches; ++i)
    printf("%d ", sol[i]);
}