Pagini recente » Cod sursa (job #131326) | Cod sursa (job #285954) | Cod sursa (job #264034) | Cod sursa (job #2323787) | Cod sursa (job #2468486)
#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, 1000);
fin.getline(b, 1000);
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);
if(s.size()==1000)
break;
}
}
fout << s.size() << '\n';
for(i=0; i<s.size(); i++)
fout << s[i] << ' ';
return 0;
}