Pagini recente » Cod sursa (job #1009637) | Cod sursa (job #1395939) | Cod sursa (job #2629033) | Cod sursa (job #1182144) | Cod sursa (job #1687262)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define P 73
#define MOD1 100007
#define MOD2 100021
#define N 2000010
#define VERIF hs11==hs21 && hs12==hs22
using namespace std;
char sir1[N],sir2[N];
int v[N];
int main(){
int p1,p2;
int hs11,hs12,hs21,hs22;
int nr=0;
int len1,len2,i;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",sir1,sir2);
len1=strlen(sir1);
len2=strlen(sir2);
hs11=hs12=0;
p1=p2=1;
for(i=0;i<len1;i++){
hs11=(hs11*P+sir1[i])%MOD1;
hs12=(hs12*P+sir1[i])%MOD2;
if(i==0){
continue;
}
p1=p1 * P % MOD1;
p2=p2 * P % MOD2;
}
hs21=hs22=0;
for(i=0;i<len1;i++){
hs21=( hs21 * P + sir2[i] )%MOD1;
hs22= (hs22 * P + sir2[i] )%MOD2;
}
if(VERIF){
v[nr++]=0;
}
for(i=len1;i<len2;i++){
hs21 = ((hs21 - (sir2[i - len1] * p1) % MOD1 + MOD1) * P + sir2[i]) % MOD1;
hs22 = ( (hs22 - (sir2[i - len1] * p2) % MOD2 + MOD2) * P + sir2[i]) % MOD2;
if(VERIF){
v[nr++]=i-len1+1;
}
}
printf("%d\n",nr);
if(nr>1000){
nr=1000;
}
for(i=0;i<nr;i++){
printf("%d ",v[i]);
}
return 0;
}