Pagini recente » Borderou de evaluare (job #2529310) | Borderou de evaluare (job #3329837) | Borderou de evaluare (job #3357292) | Borderou de evaluare (job #885435) | Cod sursa (job #3333386)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAXN=2000010;
string model,text;
int prefix[MAXN],aparitii[MAXN];
int lgModel,lgText,nrAparitii;
void construiestePrefix(){
int poz=1,lungime=0;
while(poz<lgModel){
if(model[poz]==model[lungime]){
prefix[poz++]=++lungime;
}else{
if(lungime)lungime=prefix[lungime-1];
else prefix[poz++]=0;
}
}
}
void cautaModel(){
int i=0,j=0;
while(i<lgText){
if(text[i]==model[j]){
i++;j++;
if(j==lgModel){
aparitii[++nrAparitii]=i-j;
j=prefix[j-1];
}
}else{
if(j)j=prefix[j-1];
else i++;
}
}
fout<<nrAparitii<<"\n";
if(nrAparitii>1000)nrAparitii=1000;
for(int i=1;i<=nrAparitii;i++)
fout<<aparitii[i]<<" ";
}
int main(){
fin>>model;
fin>>text;
lgModel=model.size();
lgText=text.size();
construiestePrefix();
cautaModel();
return 0;
}