Cod sursa(job #1992743)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 21 iunie 2017 12:14:09
Problema Potrivirea sirurilor Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

struct subsir{
  char lit;
  int pozUrmSuf;
}A[2000100];

char B[2000100];
int lgA, lgB;
int rez[2000100];
//B- textul in care trebuie sa cautam subsirul A
//lg- lungimile sirurilor
//rez- array care contine solutia finala

void citire(){
  in>>B;
  lgA = strlen(B);
  for(int i = 0; i < lgA; i++)
    A[i].lit = B[i];
  A[lgA].lit = '\0';
  in>>B;
  lgB = strlen(B);
}

//fct. pt. creearea unui array care contine poz urmatoare a sufixului
//care este egal cu prefixul literei corespunzatoare
void prefix(){
  int lungime = 0;//lungimea celui mai lung prefix sufix
  int indiceA = 1;
  A[0].pozUrmSuf = 0;
  while(indiceA < lgA){
    if(A[indiceA].lit == A[lungime].lit){
      lungime++;
      A[indiceA].pozUrmSuf = lungime;
      indiceA++;
    }
    else{
      if(lungime != 0){
        lungime =  A[indiceA - 1].pozUrmSuf;
      }
      else{
        A[indiceA].pozUrmSuf = 0;
        indiceA++;
      }
    }
  }
}

void potrivireSiruri(){
  int pozPlec = -1;
  int indiceA = 0, indiceB = 0;
  while(indiceB < lgB){
    if(B[indiceB] == A[indiceA].lit){//avansam cu ambii indici
      indiceA++;
      indiceB++;
    }
    if(indiceA == lgA){//am gasit o solutie
      rez[++rez[0]] = indiceB - indiceA;
      indiceA = A[indiceA - 1].pozUrmSuf;
    }
    else if(indiceB < lgB && B[indiceB] != A[indiceA].lit){
      if(indiceA != 0)
        indiceA = A[indiceA-1].pozUrmSuf;
      else
        indiceB++;
    }
  }
}

int main(){
  citire();
  prefix();
  potrivireSiruri();
  out<<rez[0]<<'\n';
  for(int i = 1; i <= rez[0]; i++)
     out<<rez[i]<<' ';
  return 0;
}