Pagini recente » Diferente pentru probleme-de-taietura intre reviziile 96 si 41 | Istoria paginii runda/practice | Istoria paginii moisil-2015/geometrie | Clasament dupa rating | Cod sursa (job #769439)
Cod sursa(job #769439)
#include <stdio.h>
#include <string.h>
#define MOD1 1000007
#define MOD2 1000021
#define BASE 73
#define MAXL 2000001
char A[MAXL], B[MAXL];
bool match[MAXL];
int main() {
FILE *f = fopen("strmatch.in", "r");
FILE *g = fopen("strmatch.out", "w");
fscanf(f, "%s %s", A, B);
int lenA = strlen(A), lenB = strlen(B);
if (lenA > lenB) {
fprintf(g, "0");
fclose(f);
fclose(g);
return 0;
}
int count = 0;
int hashA1, hashA2; //valorile hash ale substringului;
int hash1, hash2; //valorile hash ale substringului de lungime
//lenA din B
hashA1 = 0, hashA2 = 0, hash1 = 0, hash2 = 0;
int maxPow1 = 1, maxPow2 = 1;
for (int i = 0; i < lenA; i++) {
hashA1 = (hashA1 * BASE + A[i]) % MOD1;
hashA2 = (hashA2 * BASE + A[i]) % MOD2;
hash1 = (hash1 * BASE + B[i]) % MOD1;
hash2 = (hash2 * BASE + B[i]) % MOD2;
if (i != 0) {
maxPow1 = (maxPow1 * BASE) % MOD1;
maxPow2 = (maxPow2 * BASE) % MOD2;
}
}
if (hash1 == hashA1 && hash2 == hashA2) {
count++;
match[0] = true;
}
for (int i = lenA; i < lenB; i++) {
hash1 = ((hash1 - (B[i - lenA] * maxPow1) % MOD1 + MOD1) * BASE + B[i]) % MOD1;
hash2 = ((hash2 - (B[i - lenA] * maxPow2) % MOD2 + MOD2) * BASE + B[i]) % MOD2;
if (hashA1 == hash1 && hashA2 == hash2) {
count++;
match[i - lenA + 1] = true;
}
}
fprintf(g, "%d\n", count);
count = 0;
for (int i = 0; i < lenB && count < 1000; i++) {
if (match[i] == true) {
fprintf(g, "%d ", i);
}
}
fclose(f);
fclose(g);
return 0;
}