Pagini recente » Cod sursa (job #13654) | Cod sursa (job #973538) | Cod sursa (job #3218013) | Cod sursa (job #3139624) | Cod sursa (job #3206334)
#include<fstream>
#include<cstring>
#define MOD1 100007
#define MOD2 100021
using namespace std;
char s1[2000005], s2[2000005];
int rez[1001];
const int b1=127,b2=131;
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*b1+s1[i])%MOD1;
nr2=(nr2*b2+s1[i])%MOD2;
if (i>=1)
{
p1=(p1*b1)%MOD1;
p2=(p2*b2)%MOD2;
}
}
for (i=0;i<l1;i++)
{
nrs1=(nrs1*b1+s2[i])%MOD1;
nrs2=(nrs2*b2+s2[i])%MOD2;
}
if (nrs1==nr1 && nrs2==nr2)
{
rez[++cnt]=0;
}
for (i=l1;i<l2;i++)
{
nrs1=((nrs1-(p1*s2[i-l1])%MOD1+MOD1)*b1+s2[i])%MOD1;
nrs2=((nrs2-(p2*s2[i-l1])%MOD2+MOD2)*b2+s2[i])%MOD2;
if (nrs1==nr1 && nrs2==nr2)
{
cnt++;
if(cnt<=1000)
rez[cnt]=i-l1+1;
}
}
cout<<cnt<<'\n';
for (i=1;i<=1000 && i<=cnt;i++)
{
cout<<rez[i]<<" ";
}
}
return 0;
}