Pagini recente » Monitorul de evaluare | Clasament dupa rating | Clasament dupa rating | Profil AlexiaPaunescu100 | Cod sursa (job #1992743)
#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;
}