Pagini recente » preoji/clasament/9 | Cod sursa (job #429831) | Cod sursa (job #1268867) | Cod sursa (job #2519657) | Cod sursa (job #2803594)
#include <bits/stdc++.h>
using namespace std;
#define baza 73
#define mod1 1000007
#define mod2 666013
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string pat,s;
int i;
long long putere1=1,putere2=1,cod1,cod2,curr1,curr2;
int nr,rasp[2000005];
void rabin()
{
int n=pat.size();
int m=s.size();
for(i=0; i<n; i++)
{
cod1=(cod1*baza%mod1+(pat[i] ))%mod1;
cod2=(cod2*baza%mod2+(pat[i] ))%mod2;
curr1=(curr1*baza%mod1+(s[i] ))%mod1;
curr2=(curr2*baza%mod2+(s[i] ))%mod2;
if(i<n-1) {putere1*=baza;putere2*=baza;}
putere1%=mod1;
putere2%=mod2;
}
if(cod1==curr1&&cod2==curr2)
{
rasp[++nr]=0;
}
for(i=n; i<=m; i++)
{
curr1=(curr1-s[i-n]*putere1%mod1)+mod1;
curr1%=mod1;
curr1*=baza;
curr1+=(s[i] );
curr1%=mod1;
curr2=(curr2-s[i-n]*putere2%mod2)+mod2;
curr2%=mod2;
curr2*=baza;
curr2+=(s[i] );
curr2%=mod2;
if(cod1==curr1&&cod2==curr2)
{
rasp[++nr]=i-n+1;
}
}
fout<<nr<<'\n';
nr=min(nr,1000);
for(i=1;i<=nr;i++)fout<<rasp[i]<<" ";
}
int main()
{
fin>>pat>>s;
rabin();
return 0;
}