Pagini recente » Cod sursa (job #253380) | Cod sursa (job #2773350) | Cod sursa (job #2555733) | Cod sursa (job #5987) | Cod sursa (job #3200990)
#include<fstream>
#include<cstring>
#define MOD1 100007
#define MOD2 100021
using namespace std;
char s1[2000005], s2[2000005];
bool v[2000005];
int main()
{
ifstream cin ("strmatch.in");
ofstream cout("strmatch.out");
long long int l1, l2, nr1=0, nr2=0, nrs1=0, nrs2=0, p1=1, p2=1, i, cnt=0;
cin>>s1>>s2;
l1=strlen(s1);
l2=strlen(s2);
if (l1>l2)
{
cout<<'0';
}
else
{
for (i=0;i<l1;i++)
{
nr1=(nr1*73+s1[i])%MOD1;
nr2=(nr2*73+s1[i])%MOD2;
if (i>=1)
{
p1=(p1*73)%MOD1;
p2=(p2*73)%MOD2;
}
}
for (i=0;i<l1;i++)
{
nrs1=(nrs1*73+s2[i])%MOD1;
nrs2=(nrs2*73+s2[i])%MOD2;
}
if (nrs1==nr1 && nrs2==nr2)
{
v[0]=1;
cnt++;
}
for (i=l1;i<l2;i++)
{
nrs1=((nrs1-(s2[i-l1]*p1)%MOD1+MOD1)*73+s2[i])%MOD1;
nrs2=((nrs2-(s2[i-l1]*p2)%MOD2+MOD2)*73+s2[i])%MOD2;
if (nrs1==nr1 && nrs2==nr2)
{
v[i-l1+1]=1;
cnt++;
}
}
cout<<cnt<<'\n';
for (i=0;i<=1000 && i<=nrs2;i++)
{
if (v[i]==1)
{
cout<<i<<' ';
}
}
}
return 0;
}