Pagini recente » Cod sursa (job #1959503) | Cod sursa (job #2542280) | Cod sursa (job #2601128) | Cod sursa (job #2285363) | Cod sursa (job #2134186)
#include <iostream>
#include <string.h>
#define nmax 2000000
#define INF 1000000
#define MOD 1000000007
#define baz 73
using namespace std;
int mypow(int x,int p)
{
if(p==0)
return 1;
if(p==1)
return x;
long long rez=mypow(x,p/2);
if(p%2==0)
return (rez*rez)%MOD;
return (rez*rez*x)%MOD;
}
char a[nmax],b[nmax];
int ans[1001];
long long act;
int invmod(int x)
{
return mypow(x,MOD);
}
int main()
{
int n,m,i,sear=0,rez=0,p=1;
cin>>a;
cin>>b;
m=strlen(a);
n=strlen(b);
sear=a[0];
for(i=1;i<m;i++)
{
sear=(sear*baz+a[i])%MOD;
p=(p*baz)%MOD;
}
for(i=0;i<m;i++)
act=(act*baz+b[i])%MOD;
if(act==sear)
{
rez++;
ans[rez]=0;
}
for(i=m;i<n;i++)
{
act=((act-(b[i-m]*p)%MOD+MOD)*baz+b[i])%MOD;
if(act==sear)
{
rez++;
ans[rez]=i-m+1;
}
}
cout<<rez<<'\n';
for(i=1;i<=rez;i++)
cout<<ans[i]<<' ';
return 0;
}