Cod sursa(job #2807036)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 23 noiembrie 2021 12:09:52
Problema Potrivirea sirurilor Scor 70
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.4 kb
// This program was written on 23.11.2021
// for problem strmatch
// by Mircea Rebengiuc

#include <stdio.h>
#include <ctype.h>

#define MAXN 2000000
#define MAXOUT 1000

char text[MAXN];
char pat[MAXN + 2];
int lps[MAXN];

int match[MAXN];
int nmatch;

FILE *fin, *fout;

static inline int fgetint(){
  int n = 0, ch, semn = 1;

  while( isspace(ch = fgetc(fin)) );
  if( ch == '-' ){
    semn = -1;
    ch = fgetc(fin);
  }
  do
    n = n * 10 + ch - '0';
  while( isdigit(ch = fgetc(fin)) );

  return n * semn;
}

int main(){
  fin  = fopen("strmatch.in",  "r");
  fout = fopen("strmatch.out", "w");
  
  int n, m, i, j;
  
  fscanf(fin, "%s %s", pat, text);
  
  n = -1;
  while( isalpha(pat[++n]) );
    
  m = -1;
  while( isalpha(text[++m]) );

  // get lps
  lps[0] = 0;
  for( i = 1 ; i < n ; i++ ){
    j = lps[i - 1];
    while( j > 0 && pat[j] != pat[i] )
      j = lps[j - 1];
    
    lps[i] = j + (pat[i] == pat[j]);
  }
  
  // search for pattern in text
  j = nmatch = 0;
  for( i = 0 ; i < m ; i++ ){
    while( j > 0 && pat[j] != text[i] )
      j = lps[j - 1];
    
    if( text[i] == pat[j] )
      if( (++j) == n ){
        match[nmatch++] = i - n + 1;
        j = lps[j - 1];
      }
  }
  
  fprintf(fout, "%d\n", nmatch);
  nmatch = MAXOUT < nmatch ? MAXOUT : nmatch;
  for( i = 0 ; i < nmatch ; i++ )
    fprintf(fout, "%d ", match[i]);
  fputc('\n', fout);
  
  fclose(fin);
  fclose(fout);
  return 0;
}