Pagini recente » Cod sursa (job #857780) | Cod sursa (job #180886) | Cod sursa (job #1916931) | Cod sursa (job #2103726) | Cod sursa (job #2357659)
#include <cstdio>
#include <cstring>
using namespace std;
const int NMAX=2000001;
#define BASE 31
#define MOD1 100007
#define MOD2 100021
char s[NMAX],w[NMAX];
bool match[NMAX];
int cnt=0;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(w);
gets(s);
int m=strlen(w);
int n=strlen(s);
if(m>n){
printf("0\n");
return 0;
}
int hashW1=0,hashW2=0;
int hashS1=0,hashS2=0;
int P1=1,P2=1;
for(int i=0;i<m;++i){
hashW1=(hashW1*BASE+w[i])%MOD1;
hashW2=(hashW2*BASE+w[i])%MOD2;
if(i!=0){
P1=(P1*BASE)%MOD1;
P2=(P2*BASE)%MOD2;
}
}
for(int i=0;i<m;++i){
hashS1=(hashS1*BASE+s[i])%MOD1;
hashS2=(hashS2*BASE+s[i])%MOD2;
}
if(hashS1==hashW1 && hashS2==hashW2){
++cnt;
match[0]=1;
}
for(int i=m;i<n;++i){
hashS1=((hashS1-(s[i-m]*P1)%MOD1+MOD1)*BASE+s[i])%MOD1;
hashS2=((hashS2-(s[i-m]*P2)%MOD2+MOD2)*BASE+s[i])%MOD2;
if(hashS1==hashW1 && hashS2==hashW2){
++cnt;
match[i-m+1]=1;
}
}
printf("%d\n",cnt);
for(int i=0;i<n;++i)
if(match[i]==1)
printf("%d ",i);
return 0;
}