Pagini recente » Cod sursa (job #2786568) | Cod sursa (job #1193419) | Cod sursa (job #343612) | Cod sursa (job #2427780) | Cod sursa (job #1813025)
#include <cstdio>
#include <iostream>
#include <cstring>
#define lgmax 2000003
#define in "strmatch.in"
#define out "strmatch.out"
#define base 73
#define mod 100007
#define mod2 100021
typedef unsigned long long ull;
using namespace std;
ull Mx,Mx2;
ull ha,ha2,hb,hb2;
char A[lgmax],B[lgmax];
int ct=0,rez[1003];
int m,n;
int main()
{
freopen(in,"r",stdin);
freopen(out,"w",stdout);
scanf("%s %s",A,B);
m=strlen(A);
n=strlen(B);
if(m>n)
{
printf("0\n");
return 0;
}
Mx=Mx2=1;
for(int i=0; i<m; ++i)
{
ha=(ha*base +A[i])%mod;
ha2=(ha2*base +A[i])%mod2;
hb=(hb*base +B[i])%mod;
hb2=(hb2*base +B[i])%mod2;
if(i!=0) //Mx = base^(m-1) %mod , Mx2 =... %mod2
{
Mx=(Mx*base)%mod;
Mx2=(Mx2*base)%mod2;
}
}
for(int i=0; i<=n-m; ++i)
{
if(ha==hb && ha2==hb2)
{
++ct;
if(ct<=1000) rez[ct]=i;
}
hb=( ((hb - Mx*B[i])%mod +mod) * base +B[i+m] ) %mod;
hb2=( ((hb2 - Mx2*B[i])%mod2 +mod2) * base +B[i+m] ) %mod2;
}
printf("%d\n",ct);
for(int i=1; i<=min(1000,ct); ++i)
printf("%d ",rez[i]);
fclose(stdin); fclose(stdout);
return 0;
}