Pagini recente » Cod sursa (job #1311071) | Cod sursa (job #574600) | Cod sursa (job #369813) | Cod sursa (job #983423) | Cod sursa (job #1301621)
#include <fstream>
#include <string>
const long long mod1=3037000493, mod2=3037000453, base=75;
int main(){
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
std::string p,t; //pattern and text
fin>>p>>t;
if(p.size()>t.size()) 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<p.size();++i){
mostsig1=mostsig1*base%mod1;
mostsig2=mostsig2*base%mod2;
}
for(unsigned i=0;i<p.size();++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=p.size();i<t.size();++i){
ht1=( ( ht1 - mostsig1*t[i-p.size()] )*base + t[i] )%mod1;
ht2=( ( ht2 - mostsig2*t[i-p.size()] )*base + t[i] )%mod2;
if(hp1==ht1&&hp2==ht2){
if(nr<1000) out[nr]=i-p.size()+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';
}
}