Pagini recente » Cod sursa (job #2520472) | Cod sursa (job #157709) | Cod sursa (job #3223471) | Cod sursa (job #207034) | Cod sursa (job #369707)
Cod sursa(job #369707)
using namespace std;
#include <fstream>
#include <iostream>
#define MAX 2000010
#define nrPrim 666666667
char s[MAX], p[MAX];
int ns,np;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void read();
void solve();
void write();
int main(){
read();
solve();
write();
return 0;
}
void read(){
np=0;
char x;
x=fin.get();
while(x>='A' && x<='Z'){
p[++np]=x;
x=fin.get();
}
while(x<'A' || x>'Z')
x = fin.get();
ns=0;
while(x>='A' && x<='Z'){
s[++ns] = x;
x=fin.get();
}
}
int nrpoz, nrpp, poz[1010];
void solve(){
int dlam_1=1; //(d=26)^(m-1)
for(int i=1;i<np;++i)
dlam_1 =(dlam_1 *26) % nrPrim;
int hp=0 ; //hasul lui p
for(int i=1;i<=np;i++)
hp = (hp * 26 + p[i]-'A'+1) % nrPrim;
cout<<"hp = "<<hp<<endl;
int hs = 0; // hasul lui s1s2...snp, se modifica mai tarziu
for(int i=1;i<=np;i++)
hs = (hs * 26 + s[i]-'A'+1) % nrPrim;
for(int i=1;i<=ns-np+1;++i){
//cout<<i<<" "<<s[i]<<" "<<hs<<endl;
//verific protrivirea
if(hp ==hs){
nrpoz++;
if(nrpoz<=1000)
poz[++nrpp]=i-1;
}
hs = (hs-(s[i]-'A'+1)*dlam_1)%nrPrim;
hs = (hs*26+s[i+np]-'A'+1) % nrPrim;
}
}
void write(){
fout<<nrpoz<<endl;
for(int i=1;i<=nrpp;++i)
fout<<poz[i]<<" ";
}