Pagini recente » Cod sursa (job #871808) | Cod sursa (job #871821) | Cod sursa (job #1585167) | Cod sursa (job #849731) | Cod sursa (job #2803309)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
#define baza 255
#define MOD 100007
char s[2000005], t[2000005];
int k1,k2,p1=1,p2=1,x1,x2,i,s1,s2,nr;
char sol[2000005];
int main()
{
fin>>(s+1)>>(t+1);
x1=strlen(s+1);
x2=strlen(t+1);
for(i=1; i<=x1; i++)
{
k1=(k1*baza+s[i])%MOD;
k2=(k2*baza+s[i])%MOD;
if(i!=1)
{
p1=(p1*baza)%MOD;
p2=(p2*baza)%MOD;
}
}
for(i=1; i<=x1; i++)
{
s1=(s1*baza+t[i])%MOD;
s2=(s2*baza+t[i])%MOD;
}
if(s1==k1&&s2==k2)
{
sol[0]=1;
nr++;
}
for(i=x1; i<x2; i++)
{
s1=((s1-(t[i-x1+1]*p1)%MOD+MOD)*baza+t[i+1])%MOD;
s2=((s2-(t[i-x1+1]*p2)%MOD+MOD)*baza+t[i+1])%MOD;
if(s1==k1&&s2==k2)
{
sol[i-x1+1]=1;
nr++;
}
}
fout<<nr<<'\n';
for(i=1; i<=min(x2,1000); i++)if(sol[i])fout<<i<<" ";
return 0;
}