Pagini recente » Cod sursa (job #1604317) | Cod sursa (job #2737913) | Cod sursa (job #3276975) | Cod sursa (job #1071699) | Cod sursa (job #147338)
Cod sursa(job #147338)
#include <cstdio>
#include <cstring>
const long prime = 6997;
const long MAX = 2000010; // TODO : de pus la loc
char A[MAX], B[MAX];
long n,m,hash, test,nr;
long Save[1000];
bool valid(char a) {
if ( a>='A' && a<='Z' ) return true;
if ( a>='0' && a<='9' ) return true;
return false;
}
bool go_real(long x) {
char c = B[x+n]; B[x+n]=0;
long r = strcmp(B+x, A);
B[x+n] = c;
return r==0;
}
int main() {
long i;
freopen("strmatch.in", "r", stdin);
fgets(A, MAX, stdin);
fgets(B, MAX, stdin);
for (n=strlen(A); !valid(A[n]); --n) A[n]=0; ++n;
for (m=strlen(B); !valid(B[n]); --m) B[n]=0; ++m;
// calculare hash
// functie : nr in baza 256 mod un nr prim
for (i=0; i<n; ++i)
hash = (hash+A[i])%prime;
// cautam pozitii-candidat
for (i=0; i<m; ++i) {
test = (test + B[i])%prime;
if ( i>=n )
test = (prime+test-B[i-n])%prime;
if ( test==hash )
if ( go_real(i-n+1) ) {
nr ++;
if ( Save[0]<1000 )
Save[++Save[0]] = i-n+1;
}
}
freopen("strmatch.out", "w", stdout);
printf("%ld\n", nr);
for (i=1; i<=Save[0]; ++i)
printf("%ld ", Save[i]);
return 0;
}