Pagini recente » Cod sursa (job #1314534) | Cod sursa (job #1165355) | Cod sursa (job #1852590) | Cod sursa (job #2073866) | Cod sursa (job #2409941)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define ll long long
string s,p;
ll i,j,np,ns;
ll hp1,hs1,hp2,hs2,nr;
int d=73,q1=100007,q2=100021;
vector<ll>v;
int main()
{
f>>p>>s;
np=p.size();
ns=s.size();
ll putere=1;
for(i=0; i<np; i++)
{
//hp1+=(p[i]*putere)%q1;
// hs1 +=(s[i]*putere)%q1;
// hp2 +=(p[i]*putere)%q2;
//hs2 +=(s[i]*putere)%q2;
// putere=(putere*d);
hp1=(hp1*d+p[i])%q1;
hp2=(hp2*d+p[i])%q2;
hs1=(hs1*d+s[i])%q1;
hs2=(hs2*d+s[i])%q2;
}
if(hp1==hs1 && hp2==hs2 )
{
nr++;
v.push_back(0);
}
ll d_la_np1=1,d_la_np2=1;
for(i=1; i<=np-1; i++)
{
d_la_np1=(d_la_np1*d)%q1;
d_la_np2=(d_la_np2*d)%q2;
}
for(i=1; i<ns-np+1; i++)
{
hs1=(((hs1-(s[i-1]*d_la_np1))%q1+q1)*d+s[i+np-1])%q1;
hs2=(((hs2-(s[i-1]*d_la_np2))%q2+q2)*d+s[i+np-1])%q2;
g<<hs1<<' '<<hp1<<endl<<hs2<<' '<<hp2<<endl<<endl;
if(hs1==hp1 && hs2==hp2 )
{
nr++;
v.push_back(i);
}
}
g<<nr<<endl;
if(nr<=1000) for(i=0; i<nr; i++) g<<v[i]<<' ';
else for(i=0; i<1000; i++) g<<v[i]<<' ';
return 0;
}