Pagini recente » Cod sursa (job #1386099) | Cod sursa (job #824930) | Cod sursa (job #2497405) | Cod sursa (job #2308983) | Cod sursa (job #677679)
Cod sursa(job #677679)
// Infoarena - Arhiva Educationala Potrivirea Sirurilor
// Februrie 2012 Marius Dumitran
// Rabin Karp O(n+m)
#include<string.h>
#include<stdio.h>
#define maxn (1<<21)
#define prim1 100007
#define prim2 100021
char sir1[ maxn ], sir2[ maxn ];
int sol[ 2000 ];
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", sir1, sir2);
int n = strlen(sir1), m = strlen(sir2), nr = 0;
if( n > m ) {
printf("0\n");
return 0;
}
int hash1 = 0, hash2 = 0, hash3 = 0 , hash4 = 0, val1 = 1, val2 = 1;
for (int i = 0; i < n; ++i) {
hash1 = (hash1 * 27 + sir1[i]-'A') % prim1;
hash2 = (hash2 * 27 + sir1[i]-'A') % prim2;
hash3 = (hash3 * 27 + sir2[i]-'A') % prim1;
hash4 = (hash4 * 27 + sir2[i]-'A') % prim2;
if( i != 0)
val1 = val1 * 27 % prim1, val2 = val2 * 27 % prim2;
}
if( hash3 == hash1 && hash2 == hash4 ) {
sol[nr++] = 0;
}
for( int i = n; i <= m; ++i ){
int temp1 = hash3 + prim1 - val1 * (sir2[ i-n] - 'A');
int temp2 = hash4 + prim2 - val1 * (sir2[ i-n] - 'A');
hash3 = ((temp1 % prim1) * 27 + sir2[i] - 'A') % prim1;
hash4 = ((temp2 % prim2) * 27 + sir2[i] - 'A') % prim2;
if( hash3 == hash1 && hash2 == hash4 ) {
if( nr > 1000 )
nr++;
else
sol[nr++] = i - n + 1;
}
}
printf("%d\n", nr);
for( int i = 0; i < nr && i < 1000; ++i)
printf("%d ", sol[i]);
printf("\n");
return 0;
}