Pagini recente » Cod sursa (job #4430) | Borderou de evaluare (job #893670) | Cod sursa (job #1766615) | Cod sursa (job #2283923) | Cod sursa (job #1992750)
#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;
}