Pagini recente » Cod sursa (job #2592880) | Cod sursa (job #285837) | Cod sursa (job #34842) | Cod sursa (job #2851456) | Cod sursa (job #3199693)
#include <iostream>
#include <fstream>
#include <cstring>
#define int long long
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int mod=1e9+13,p=257;
char a[2000001],b[2000001];
int hasha[2000001],hashb[2000001],put[2000001],sol[2000001];
int32_t main()
{
fin>>a>>b;
int n=strlen(a);
put[0]=1;
/**copiaza si asta**/
hasha[0]=0;
for (int i=1;i<=n;i++)
{
hasha[i]=hasha[i-1]*p+a[i-1];
hasha[i]%=mod;
put[i]=put[i-1]*p%mod;
//cout<<hasha[i]<<" ";
}
//cout<<'\n';
hashb[0]=0;
int m=strlen(b);
for (int i=1;i<=m;i++)
{
hashb[i]=hashb[i-1]*p+b[i-1];
hashb[i]%=mod;
//cout<<hashb[i]<<" ";
}
//cout<<'\n';
int nr=0;
for (int i=0;i<strlen(b);i++)
{
int k=((hashb[i+n-1]-hashb[i-1]*put[n])%mod+mod)%mod;
if (k==hasha[n]) sol[++nr]=i-1;
}
fout<<nr<<'\n';
for (int i=1;i<=nr;i++)
fout<<sol[i]<<' ';
return 0;
}