Pagini recente » Cod sursa (job #1247661) | Cod sursa (job #2197263) | Cod sursa (job #2511175) | Cod sursa (job #2756521) | Cod sursa (job #1247004)
#include <cstdio>
#include <cstring>
#include <cmath>
#define q 71
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 = 52;
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);
gets(pattern);
gets(Text);
Rabin_Karp(pattern,Text);
printf("%d\n",nr);
for(register int i=1;i<=k;++i)
printf("%d ",Sol[i]);
return 0;
}