Pagini recente » Cod sursa (job #599602) | Cod sursa (job #269369) | Cod sursa (job #318684) | Cod sursa (job #1611778) | Cod sursa (job #2427988)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 2000005
#define MOD 666013
long hash(char *str, int len) {
long hash = 0;
for(int i = 0; i < len; ++i) {
hash = (hash * 32 + str[i]) % MOD;
}
return hash;
}
int main() {
char text[MAXN], sablon[MAXN];
int sol[10000], k = 0;
FILE *in = fopen("strmatch.in", "r");
fgets(sablon, MAXN, in);
fgets(text, MAXN, in);
fclose(in);
int n = strlen(text) - 1, m = strlen(sablon) - 1;
sablon[m] = 0;
text[n] = 0;
long hash_sablon = 0, rolling_hash = 0;
for(int i = 0; i < m; ++i) {
hash_sablon = (hash_sablon * 32 + sablon[i]) % MOD;
rolling_hash = (rolling_hash * 32 + text[i]) % MOD;
}
long pow = 1;
for(int i = 1; i <= m - 1; ++i) {
pow *= 32;
}
if(hash_sablon == rolling_hash) {
printf("%d ", 0);
return 0;
}
for(int i = 1; i < n - m + 1; ++i) {
rolling_hash = (((rolling_hash + 32 * MOD - pow * text[i - 1]) * 32) % MOD + text[i + m - 1]) % MOD;
if(rolling_hash == hash_sablon) {
int ok = 1;
for(int j = 0; j < m; ++j) {
if(sablon[j] != text[i + j]) {
ok = 0;
break;
}
}
if(ok) {
sol[k++] = i;
//printf("Am gasit la %d\n", i);
}
}
}
FILE *out = fopen("strmatch.out", "w");
fprintf(out, "%d\n", k);
for(int i = 0; i < k; ++i) {
fprintf(out, "%d ", sol[i]);
}
fprintf(out, "\n");
fclose(out);
}