Pagini recente » Cod sursa (job #1932336) | Cod sursa (job #1493460) | Cod sursa (job #1794259) | Cod sursa (job #2364967) | Cod sursa (job #2468531)
#include <bits/stdc++.h>
#define B 128
#define m1 100007
#define m2 100003
#define Nmax 2000005
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char a[Nmax], b[Nmax];
vector <int> s;
int n, m, i;
long long ha1, ha2, hb1, hb2, p1, p2;
int main()
{
fin.getline(a, Nmax);
fin.getline(b, Nmax);
n=strlen(a);
m=strlen(b);
p1=p2=1;
for(i=0; i<n; i++)
{
ha1=(ha1*B+a[i])%m1;
ha2=(ha2*B+a[i])%m2;
hb1=(hb1*B+b[i])%m1;
hb2=(hb2*B+b[i])%m2;
if(i)
{
p1=(p1*B)%m1;
p2=(p2*B)%m2;
}
}
if(ha1==hb1&&ha2==hb2)
s.push_back(0);
for(i=1; i<=m-n; i++)
{
hb1=(((hb1-(p1*b[i-1])%m1+m1)%m1)*B+b[i+n-1])%m1;
hb2=(((hb2-(p2*b[i-1])%m2+m2)%m2)*B+b[i+n-1])%m2;
if(ha1==hb1&&ha2==hb2)
s.push_back(i);
}
n=s.size();
fout << n << '\n';
for(i=0; i<max(n, 1000); i++)
fout << s[i] << ' ';
return 0;
}