Pagini recente » Cod sursa (job #2939017) | Cod sursa (job #432204) | Cod sursa (job #2776701) | Borderou de evaluare (job #2510167) | Cod sursa (job #530999)
Cod sursa(job #530999)
#include <cstdio>
#include <string>
using namespace std;
#define MAXN 2000001
#define MAX_MATCHES 1000
#define PRIME_MULT 101
#define PRIME_MOD1 573527
#define PRIME_MOD2 574297
char A[MAXN], B[MAXN];
int lenA, lenB, matches, indices[MAX_MATCHES];
int main()
{
int hashA1, hashA2, hashB1, hashB2, pow1, pow2;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", A, B);
lenA = strlen(A); lenB = strlen(B);
if (lenA > lenB) {
printf("0\n");
return 0;
}
hashA1 = hashA2 = A[0], hashB1 = hashB2 = B[0]; pow1 = pow2 = 1;
for (int i = 1; i < lenA; i++) {
hashA1 = (hashA1 * PRIME_MULT + A[i]) % PRIME_MOD1;
hashA2 = (hashA2 * PRIME_MULT + A[i]) % PRIME_MOD2;
hashB1 = (hashB1 * PRIME_MULT + B[i]) % PRIME_MOD1;
hashB2 = (hashB2 * PRIME_MULT + B[i]) % PRIME_MOD2;
pow1 = (pow1*PRIME_MULT) % PRIME_MOD1;
pow2 = (pow2*PRIME_MULT) % PRIME_MOD2;
}
if (hashA1 == hashB1 && hashA2 == hashB2) {
indices[matches++] = 0;
}
for (int i = lenA; i < lenB; i++)
{
hashB1 = ((hashB1 - (B[i - lenA] * pow1) % PRIME_MOD1 + PRIME_MOD1) * PRIME_MULT + B[i]) % PRIME_MOD1;
hashB2 = ((hashB2 - (B[i - lenA] * pow2) % PRIME_MOD2 + PRIME_MOD2) * PRIME_MULT + B[i]) % PRIME_MOD2;
if (hashA1 == hashB1 && hashA2 == hashB2) {
if (matches<MAX_MATCHES) {
indices[matches] = i-lenA+1;
}
matches++;
}
}
printf("%d\n", matches);
int limit = (matches<=MAX_MATCHES)?matches:MAX_MATCHES;
for (int i=0;i<limit;i++) {
printf("%d ",indices[i]);
}
printf("\n");
return 0;
}