Pagini recente » Cod sursa (job #1140815) | Cod sursa (job #468749) | Cod sursa (job #60508) | Cod sursa (job #1245613) | Cod sursa (job #1814217)
#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 hashA1,hashA2,hash1,hash2;
char A[lgmax],B[lgmax];
bool match[lgmax];
int m,n;
int main()
{
freopen(in,"r",stdin);
freopen(out,"w",stdout);
scanf("%s %s",A,B);
m=strlen(A);
n=strlen(B);
Mx=Mx2=1;
hashA1=hashA2=0;
for(int i=0; i<m; ++i)
{
hashA1=(hashA1*base +A[i])%mod;
hashA2=(hashA2*base +A[i])%mod2;
if(i!=0)
{
Mx=(Mx*base)%mod;
Mx2=(Mx2*base)%mod2;
}
}
if(m>n)
{
printf("0\n");
return 0;
}
for(int i=0; i<m; ++i)
hash1=(hash1*base +B[i])%mod,
hash2=(hash2*base +B[i])%mod2;
int Nr=0;
for(int i=0; i<=n-m; ++i)
{
if(hash1==hashA1 && hash2==hashA2)
match[i]=1, ++Nr;
hash1=( (hash1 - (B[i]*Mx) %mod +mod ) * base +B[i+m] ) %mod;
hash2=( (hash2 - (B[i]*Mx2)%mod2 +mod2) * base +B[i+m] ) %mod2;
}
printf("%d\n",Nr);
Nr=0;
for(int i=0; i<n && Nr<=1000; ++i)
if(match[i]==1)
++Nr,
printf("%d ",i);
fclose(stdin); fclose(stdout);
return 0;
}