Cod sursa(job #1976253)

Utilizator TincaMateiTinca Matei TincaMatei Data 2 mai 2017 23:27:30
Problema Potrivirea sirurilor Scor 62
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <cstdio>
#include <ctype.h>

char getch(FILE *fin) {
  char ch = fgetc(fin);
  while(ch == ' ')
    ch = fgetc(fin);
  return ch;
}

const int MAX_N = 2000000;
char word[1+MAX_N+1+MAX_N];
int v[1+MAX_N+1+MAX_N];
int top;
int r[1000];

inline void kmp(int n1, int n2) {
  word[n1 + 1] = -1;
  for(int i = 2; i <= n1 + n2 + 1; ++i) {
    int j = i - 1;
    while(j > 0 && word[i] != word[v[j] + 1])
      j = v[j];

    if(word[v[j] + 1] == word[i])
      v[i] = v[j] + 1;
    else
      v[i] = 0;

    if(v[i] == n1) {
      if(top < 1000)
        r[top] = i - 1 - 2 * n1;
      top++;
    }
  }
}

int main() {
  int n1, n2;
  FILE *fin = fopen("strmatch.in", "r");
  n1 = n2 = 0;
  char ch = getch(fin);
  while(isalpha(ch)) {
    word[++n1] = ch;
    ch = getch(fin);
  }
  ch = getch(fin);
  while(isalpha(ch)) {
    ++n2;
    word[n1 + 1 + n2] = ch;
    ch = getch(fin);
  }
  fclose(fin);

  kmp(n1, n2);

  FILE *fout = fopen("strmatch.out", "w");
  fprintf(fout, "%d\n", top);
  for(int i = 0; i < top && i < 1000; ++i)
    fprintf(fout, "%d ", r[i]);
  fclose(fout);
  return 0;
}