Pagini recente » Clasament Urmasii lui Moisil 2016 Clasa 9 | Cod sursa (job #786585) | Profil alex.cojocaru | Cod sursa (job #3293556) | Cod sursa (job #1247005)
#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);
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;
}