Cod sursa(job #1992750)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 21 iunie 2017 12:29:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 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[2100000];

char B[2100000];
int lgA, lgB;
int rez[2100000];
//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 pozSt = 0, pozDr = 1;
  A[0].pozUrmSuf = 0;//in fata nu indeplineste nimic conditia
  while(pozDr < lgA){
    if(A[pozSt].lit == A[pozDr].lit){
      A[pozDr].pozUrmSuf = pozSt + 1;
      pozSt ++;
      pozDr ++;
      //avansez cu ambii indici, pt ca am gasit pimul suf = pref
    }
    else{
      if(pozSt == 0){
        pozDr++;
      }
      else//exista posibilitatea ca sa existe un suf = pref literei
          pozSt = A[pozSt - 1].pozUrmSuf;
    }
  }
}

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 <=1000; i++)
     out<<rez[i]<<' ';
  return 0;
}