Pagini recente » Cod sursa (job #2872285) | Cod sursa (job #51935) | Cod sursa (job #2917413) | Cod sursa (job #1116200) | Cod sursa (job #1247017)
#include <cstdio>
#include <cstring>
#include <cmath>
#define q 666019
int n,m,nr,k;
char Text[2000001];
char pattern[2000001];
int Sol[2000000];
void Rabin_Karp(char *s1, char* s2){
int P = 0;
int T = 0;
m = strlen(s1);
n = strlen(s2);
int hashf = 1;
int ALPHABET = 123;
for(register int i=1;i<m;++i)
hashf = hashf*ALPHABET;
hashf = hashf%q;
for(register int i=0;i<m;++i){
P = (P*ALPHABET + s1[i]) % q;
T = (T*ALPHABET + s2[i]) % q;
}
for(register int i=0; i<=n-m;++i){
if(P == T){
int j;
for(j=0;j<m;++j)
if(s1[j] != s2[i+j])
break;
if(j == m){
Sol[++k] = i;
nr++;
}
}
T = (T + ALPHABET*q - s2[i]*hashf)%q;
T = (T*ALPHABET + s2[i+m])%q;
}
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",pattern);
scanf("%s",Text);
Rabin_Karp(pattern,Text);
printf("%d\n",nr);
for(register int i=1;i<=k;++i)
printf("%d ",Sol[i]);
return 0;
}