Pagini recente » Cod sursa (job #2153578) | Cod sursa (job #1643087) | Cod sursa (job #1987249) | Cod sursa (job #147719) | Cod sursa (job #3286442)
#include <fstream>
#include <cstring>
#define int long long
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m, hasha, hsh[2000005], ans[1005], i, base=127, p[2000005], mod=1000000007, nr;
char a[2000005], b[2000005];
signed main()
{
fin>>a>>b;
n=strlen(a);
m=strlen(b);
p[0]=1;
for(i=1; i<=m; i++)
p[i]=(p[i-1]*base)%mod;
for(i=0; i<n; i++)
hasha=(hasha*base+(a[i]-'0'))%mod;
for(i=0; i<m; i++)
hsh[i+1]=(hsh[i]*base+(b[i]-'0'))%mod;
for(i=n; i<=m; i++)
{
int val=(hsh[i]-(hsh[i-n]*p[n]%mod)+mod)%mod;
if(val==hasha)
{
nr++;
if(nr<=1000)
ans[nr]=i-n;
}
}
fout<<nr<<'\n';
for(i=1; i<=min(1ll*1000, nr); i++)
fout<<ans[i]<<" ";
return 0;
}