Pagini recente » Cod sursa (job #2945215) | Cod sursa (job #556161) | Cod sursa (job #2625689) | Cod sursa (job #316711) | Cod sursa (job #3300616)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define int long long
char A[2000006];
char B[2000006];
int mod1=100007;
int mod2=100021;
vector<int>v;
int32_t 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
int64_t ha1=0,p1=1;
int64_t ha2=0,p2=1;
for(int i=0;i<na;i++){
ha1=((int64_t)(ha1*73)+A[i])%mod1;
ha2=((int64_t)(ha2*73)+A[i])%mod2;
///retin puterea max fol pt fiec hash
if(i!=0){
p1=(int64_t)(p1*73)%mod1;
p2=(int64_t)(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=((int64_t)(hb1*73)+B[i])%mod1;
hb2=((int64_t)(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=(int64_t)(B[i-na]*p1)%mod1;//ce tai
int val_hash_atm=hb1-val_ch_ex+mod1;//hashul cu pr ch taiat
hb1=((int64_t)(val_hash_atm*73)+B[i])%mod1;//adaug noul ch
val_ch_ex=(int64_t)(B[i-na]*p2)%mod2;//ce tai
val_hash_atm=(hb2-val_ch_ex+mod2)%mod2;//hashul cu pr ch taiat
hb2=((int64_t)(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;
}