Pagini recente » Cod sursa (job #2718425) | Cod sursa (job #1401334) | Cod sursa (job #2689181) | Cod sursa (job #2520724) | Cod sursa (job #2084144)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define lim 2000010
unsigned int k,hashA,rez[lim],p[lim],n,m,hashB[lim],hashh;
string A,B;
int main()
{
fin>>A>>B;
n=A.size();
m=B.size();
p[0]=1;
for (int i=1; i<=m+2; i++) p[i]=p[i-1]*211;
for (int i=0; i<n; i++) hashA+=(A[i]-'0')*p[i];
for (int i=0; i<m; i++) hashB[i]=p[i]*(B[i]-'0');
for (int i=1; i<m; i++) hashB[i]+=hashB[i-1];
k=0;
hashA*=p[m-n];
for (int i=n-1; i<m; i++)
{
hashh=hashB[i]-hashB[i-n];
hashh*=p[m-i-1];
if (k<=1000 && hashh==hashA)
rez[++k]=i-n+1;
}
fout<<k<<'\n';
for (int i=1; i<=k; i++)
fout<<rez[i]<<' ';
return 0;
}