Cod sursa(job #2487893)

Utilizator alex.cojocaruAlex Cojocaru alex.cojocaru Data 5 noiembrie 2019 20:45:55
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <stdio.h>
#include <string.h>
#include <vector>

#define NMAX 2000000

char s1 [ NMAX + 1 ] ; 
char s2 [ NMAX + 1 ] ; 
std::vector <int> poz ;  
int lsp [ NMAX + 1 ] ; // longest proper prefix that is also a suffix lol 

int main () {
  FILE *fin, *fout ;
  fin = fopen ("strmatch.in", "r") ;
  fout = fopen ("strmatch.out", "w") ;  
  int n, i, m, x, counter ; 
  fscanf (fin, "%s", s1+1) ; 
  fscanf (fin, "%s", s2+1) ;

  n = strlen(s1+1) ;
  m = strlen(s2+1) ;   
  
  lsp[0] = 0 ;
  lsp[1] = 0 ;    
 
  for (i = 2 ; i <= n ; i++) {
    x = lsp[i-1] ; 
    while (x > 0 && s1[x+1] != s1[i])
      x = lsp[x] ; 
    if (s1[x+1] == s1[i])
      lsp[i] = x + 1 ;
    else
      lsp[i] = 0 ;   
  }
  x = 0 ;
  counter = 0 ;  
  for (i = 0 ; i <= m ; i++) {
    while (x > 0 && s1[x+1] != s2[i]) 
      x = lsp[x] ;
    if (s1[x+1] == s2[i]) 
      x++; 
    else 
      x = 0 ; 
    if (x == n) { 
      counter++;  
      poz.push_back(i-n) ;
    }
  }
  fprintf(fout, "%d\n", counter); 
  for (i = 0 ; i < poz.size() ; i++)
    fprintf(fout, "%d ", poz[i]) ; 
  return 0 ; 
}