Pagini recente » Cod sursa (job #1470342) | Cod sursa (job #1504529) | Cod sursa (job #324718) | Cod sursa (job #1869880) | Cod sursa (job #1468992)
#include <cstdio>
#include <cstring>
#define LMAX 2000007
#define MOD 100007
#define MOD2 100927
using namespace std;
char a[LMAX],b[LMAX];
int p[LMAX],p2[LMAX],h1[100023],cat;
int main()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
scanf("%s",a);
scanf("%s",b);
int p1=strlen(a);
int pl2=strlen(b);
p[0]=1;
p2[0]=1;
for(int i=1;i<p1;i++)
{
p[i]=p[i-1]*74;
p[i]%=MOD;
p2[i]=p2[i-1]*74;
p2[i]%=MOD2;
}
int val=0,val2=0,key=0,key2=0;
for(int i=0;i<p1;i++)
{
val+=(long long)p[p1-i-1]*(a[i]-'0');
val%=MOD;
val2+=(long long)p2[p1-i-1]*(a[i]-'0');
val2%=MOD2;
key+=(long long)p[p1-i-1]*(b[i]-'0');
key2+=(long long)p2[p1-i-1]*(b[i]-'0');
key%=MOD;
key2%=MOD2;
}
if(val2==key2&&val==key) h1[++cat]=0;
for(int i=p1;i<pl2;i++)
{
key=key-((long long)(p[p1-1]*(b[i-p1]-'0'))%MOD)+MOD;
key2=key2-((long long)(p2[p1-1]*(b[i-p1]-'0'))%MOD2)+MOD2;
key*=74;
key%=MOD;
key2*=74;
key2%=MOD2;
key+=(b[i]-'0');
key2+=(b[i]-'0');
key%=MOD;
key2%=MOD2;
if(val2==key2&&val==key) h1[++cat]=i-p1+1;
//printf("%lld\n",key);
}
printf("%d\n",cat);
if(cat>1000) cat=1000;
for(int i=1;i<=cat;i++) printf("%d ",h1[i]);
}