Pagini recente » Cod sursa (job #2496931) | Cod sursa (job #1554232) | Cod sursa (job #1637853) | Cod sursa (job #2889589) | Cod sursa (job #147397)
Cod sursa(job #147397)
#include <cstdio>
#include <cstring>
const long pr1 = 136069;
const long pr2 = 136067;
const long MAX = 2000010; // TODO : de pus la loc
const long t = 101;
char A[MAX], B[MAX];
long n,m, nr;
long hash1, hash2, test1, test2;
long Save[1002];
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) {
return true;
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
long md1=1, md2=1;
for (i=0; i<n; ++i) {
hash1 = (hash1*t+A[i])%pr1;
hash2 = (hash2*t+A[i])%pr2;
if (i) { md1 = (md1*t)%pr1; md2 = (md2*t)%pr2; }
}
// cautam pozitii-candidat
for (i=0; i<m; ++i) {
if ( i<n ) {
test1 = (test1*t + B[i])%pr1;
test2 = (test2*t + B[i])%pr2;
} else {
test1 = ((pr1+test1-(B[i-n]*md1)%pr1)*t+B[i])%pr1;
test2 = ((pr2+test2-(B[i-n]*md2)%pr2)*t+B[i])%pr2;
if ( test1==hash1 && test2==hash2 )
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;
}