Pagini recente » Cod sursa (job #1949355) | Cod sursa (job #40028) | Cod sursa (job #3033403) | Cod sursa (job #889707) | Cod sursa (job #1301638)
#include <fstream>
const unsigned MAXN=2000001;
const long long mod1=3037000493, mod2=3037000453, 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{
long long hp1=0,hp2=0;
long long ht1=0,ht2=0;
long long 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';
}
}