Pagini recente » Cod sursa (job #2467429) | Cod sursa (job #3281616) | Cod sursa (job #3175594) | Cod sursa (job #2610741) | Cod sursa (job #3171669)
#include <bits/stdc++.h>
#define mod1 100007
#define mod2 100021
#define P 73
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000200], b[2000200];
long long nrh1,nr1h1, nrh2, nr1h2;
long fr, ans[2000200];
int main()
{
fin.getline(a,2000200);
fin.getline(b,2000200);
long long exp1=1, exp2=1;
int n=strlen(a), m=strlen(b);
for(int i=0;i<n;++i)
{
nrh1=(nrh1*P+b[i])%mod1;
nrh2=(nrh2*P+b[i])%mod2;
nr1h1=(nr1h1*P+a[i])%mod1;
nr1h2=(nr1h2*P+a[i])%mod2;
if(i!=0){
exp1=exp1*P%mod1;
exp2=exp2*P%mod2;
}
}
if(nr1h1==nrh1 && nrh2==nr1h2)
{
++fr;
ans[fr]=0;
}
for(int i=n;i<m;++i)
{
nrh1=(((nrh1-b[i-n]*exp1)%mod1+mod1)*P+b[i])%mod1;
nrh2=(((nrh2-b[i-n]*exp2)%mod2+mod2)*P+b[i])%mod2;
if(nr1h1==nrh1 && nr1h2==nrh2 )
{
++fr;
ans[fr]=i-n+1;
}
}
fout<<fr<<'\n';
for(int i=1;i<=fr && i<=1000;++i)
fout<<ans[i]<<" ";
return 0;
}