Pagini recente » Cod sursa (job #682085) | Cod sursa (job #540428) | Cod sursa (job #3250503) | Cod sursa (job #1596518) | Cod sursa (job #2409897)
#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=97,q1=666013,q2=919393;
vector<ll>v;
int main()
{
f>>p>>s;
np=p.size();
ns=s.size();
ll putere=1;
for(i=np-1; i>=0; i--)
{
hp1+=(p[i]*putere)%q1;
hs1 +=(s[i]*putere)%q1;
hp2 +=(p[i]*putere)%q2;
hs2 +=(s[i]*putere)%q2;
putere=(putere*d);
}
if(hp1==hs1 && hp2==hs2 )
{
nr++;
v.push_back(0);
}
ll d_la_np=1;
for(i=1; i<=np-1; i++)
{
d_la_np=d_la_np*d;
}
for(i=1; i<ns-np+1; i++)
{
hs1=((hs1-s[i-1]*d_la_np)*d+s[i+np-1])%q1;
hs2=((hs2-s[i-1]*d_la_np)*d+s[i+np-1])%q2;
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;
}