Pagini recente » Cod sursa (job #2558461) | Cod sursa (job #3300589)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000006];
char B[2000006];
int mod1=100007;
int mod2=100021;
vector<int>v;
int main()
{
v.reserve(1000);
fin.getline(A,2000006);
fin.getline(B,2000006);
int na=strlen(A);
int nb=strlen(B);
///daca lenA>lenB => nu merge
if(na>nb){
fout<<0;
return 0;
}
///il hashuiesc pe A cu m1 si m2
int ha1=0,p1=1;
int ha2=0,p2=1;
for(int i=0;i<na;i++){
ha1=(ha1*73+A[i])%mod1;
ha2=(ha2*73+A[i])%mod2;
///retin puterea max fol pt fiec hash
if(i!=0){
p1=(p1*73)%mod1;
p2=(p2*73)%mod2;
}
}
///il hashuiesc pe B treptat cu m1 si m2
///fac pt primele na char din B ca sa am "baza" de le care plec
int hb1=0;
int hb2=0;
for(int i=0;i<na;i++){
hb1=(hb1*73+B[i])%mod1;
hb2=(hb2*73+B[i])%mod2;
}
///daca se potrivesc ambele prime hashuri
if(ha1==hb1 && ha2==hb2){
v.push_back(0);
}
///trec prin restul din B
for(int i=na;i<nb;i++){
///tai val primului ch si adaug inca unul la fin
int val_ch_ex=(B[i-na]*p1)%mod1;//ce tai
int val_hash_atm=hb1-val_ch_ex+mod1;//hashul cu pr ch taiat
hb1=(val_hash_atm*73+B[i])%mod1;//adaug noul ch
val_ch_ex=(B[i-na]*p2)%mod2;//ce tai
val_hash_atm=(hb2-val_ch_ex+mod2)%mod2;//hashul cu pr ch taiat
hb2=(val_hash_atm*73+B[i])%mod2;//adaug noul ch
///verif daca se pupa
if(ha1==hb1 && ha2==hb2 && v.size()<1000){
v.push_back(i-na+1);//bag poz de inceput a subsirului
}
}
fout<<v.size()<<'\n';
for(int i=0;i<v.size();i++){
fout<<v[i]<<" ";
}
return 0;
}