Pagini recente » Cod sursa (job #2797262) | Cod sursa (job #636293) | Cod sursa (job #207758) | Cod sursa (job #1380689) | Cod sursa (job #1918573)
#include <bits/stdc++.h>
using namespace std;
#define b1 83
#define b2 73
#define mod1 12345
#define mod2 10017
int ans[10001],cnt,i,n1,n2,hsh1,hsh2,ch1,ch2,p1,p2,ok;
char s1[2000001],s2[2000001];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(s1);
gets(s2);
n1=strlen(s1)-1;
n2=strlen(s2)-1;
p1=p2=1;
for(i=0;i<=n1;i++)
{
if(i!=0)
{
p1=(p1*b1)%mod1;
p2=(p2*b2)%mod2;
}
hsh1=(hsh1*b1+(s1[i]-'0'))%mod1;
hsh2=(hsh2*b2+(s1[i]-'0'))%mod2;
}
for(i=0;i<=n1;i++)
if(i<=n1)
{
ch1=(ch1*b1+(s2[i]-'0'))%mod1;
ch2=(ch2*b2+(s2[i]-'0'))%mod2;
}
for(i=n1+1;i<=n2;i++)
{
if(ch1==hsh1&&ch2==hsh2)
{
if(cnt+1<=1000)
ans[++cnt]=i-n1-1;
else
cnt++;
}
ch1=(b1*(ch1-((s2[i-n1-1]-'0')*p1)%mod1+mod1)+(s2[i]-'0'))%mod1;
ch2=(b2*(ch2-((s2[i-n1-1]-'0')*p2)%mod2+mod2)+(s2[i]-'0'))%mod2;
}
if(ch1==hsh1&&ch2==hsh2)
{
if(cnt+1<=1000)
ans[++cnt]=i-n1-1;
else
cnt++;
}
printf("%d\n",cnt);
for(i=1;i<=min(cnt,1000);i++)
printf("%d ",ans[i]);
return 0;
}