Pagini recente » Cod sursa (job #507196) | Cod sursa (job #669733) | Cod sursa (job #1886527) | Cod sursa (job #1263690) | Cod sursa (job #369725)
Cod sursa(job #369725)
using namespace std;
#include <fstream>
#include <iostream>
#define MAX 2000010
#define nrLitere (26+26+10)
#define nrPrim 100021
char s[MAX], p[MAX];
int ns,np;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void read();
void solve();
void write();
int ord(char c);
int main(){
read();
/*
for(int i=1;i<=np;i++)
cout<<p[i];
cout<<endl;
for(int i =1;i<=ns;i++)
cout<<s[i];
cout<<endl;
*/
solve();
write();
return 0;
}
int isOk(char c){
if(c>='A' && c<='Z')
return 1;
if(c>='a' && c<='z')
return 1;
if(c>='0' && c<='9')
return 1;
return 0;
}
void read(){
np=0;
char x;
x=fin.get();
while(isOk(x)){
p[++np]=x;
x=fin.get();
}
while(!isOk(x))
x = fin.get();
ns=0;
while(isOk(x)){
s[++ns] = x;
x=fin.get();
}
}
int nrpoz, nrpp, poz[1010];
void solve(){
int dlam_1=1; //(d=nrLitere)^(np-1)
for(int i=1;i<np;++i)
dlam_1 =(dlam_1 *nrLitere) % nrPrim;
int hp=0 ; //hasul lui p
for(int i=1;i<=np;i++)
hp = (hp * nrLitere + ord(p[i])) % 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 * nrLitere + ord(s[i])) % nrPrim;
for(int i=1;i<=ns-np+1;++i){
//cout<<i<<" "<<s[i]<<" "<<hs<<endl;
//verific protrivirea
if(hp ==hs && s[i+np-1]==p[np]){
nrpoz++;
if(nrpoz<=1000)
poz[++nrpp]=i-1;
}
hs = (hs + nrLitere*nrPrim-(ord(s[i])*dlam_1)%nrPrim)%nrPrim;
hs = (hs*nrLitere+ord(s[i+np])) % nrPrim;
}
}
void write(){
fout<<nrpoz<<endl;
for(int i=1;i<=nrpp;++i)
fout<<poz[i]<<" ";
}
int ord(char c){
if(c<='9')
return c-'0';
if(c<='Z')
return 10+c-'A';
return 10+26+c-'a';
}