Pagini recente » Cod sursa (job #693871) | Cod sursa (job #1195798) | Cod sursa (job #1921348) | Cod sursa (job #101849) | Cod sursa (job #1301646)
#include <fstream>
const unsigned MAXN=2000001;
//const int mod1=3037000493, mod2=3037000453, base=75;
const int mod1=46337, mod2=46327, base=75;
int main(){
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
char p[MAXN],t[MAXN]; //pattern and text
fin.get(p,MAXN); fin.get();
fin.get(t,MAXN);
unsigned ps=0,ts=0;
while(p[ps]) p[ps++]-='0';
while(t[ts]) t[ts++]-='0';
if(ps>ts) fout<<"0\n\n";
else{
int hp1=0,hp2=0;
int ht1=0,ht2=0;
int mostsig1=1,mostsig2=1;
for(unsigned i=1;i<ps;++i){
mostsig1=mostsig1*base%mod1;
mostsig2=mostsig2*base%mod2;
}
for(unsigned i=0;i<ps;++i){
hp1 = (hp1*base + p[i]) % mod1;
hp2 = (hp2*base + p[i]) % mod2;
ht1 = (ht1*base + t[i]) % mod1;
ht2 = (ht2*base + t[i]) % mod2;
}
unsigned nr=0;
unsigned out[1000];
if(hp1==ht1&&hp2==ht2){
out[nr++]=0;
}
for(unsigned i=ps;i<ts;++i){
ht1=(((ht1 - mostsig1*t[i-ps])%mod1+mod1 )*base + t[i] )%mod1;
ht2=(((ht2 - mostsig2*t[i-ps])%mod2+mod2 )*base + t[i] )%mod2;
if(hp1==ht1&&hp2==ht2){
if(nr<1000) out[nr]=i-ps+1;
++nr;
}
}
fout<<nr<<'\n';
unsigned m=1000; if(nr<m) m=nr;
for(unsigned i=0;i<m;++i) fout<<out[i]<<' ';
fout<<'\n';
}
}