Pagini recente » Cod sursa (job #18836) | Cod sursa (job #2472365) | Cod sursa (job #1877525) | Cod sursa (job #2982490) | Cod sursa (job #1918346)
#include <bits/stdc++.h>
using namespace std;
#define b1 101
#define b2 83
#define mod1 12345
#define mod2 10017
int cnt,i,n1,n2,hsh1,hsh2,ch1,ch2,p1,p2,ok;
char s1[2000001],s2[2000001],ans[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)
ans[i-n1-1]=1,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)
ans[++cnt]=i-n1-1;
printf("%d\n",cnt);
for(i=1;i<=n2;i++)
if(ans[i]==1)
printf("%d ",i);
return 0;
}