Pagini recente » Cod sursa (job #2059025) | Cod sursa (job #615738) | Cod sursa (job #1909054) | Cod sursa (job #446700) | Cod sursa (job #530096)
Cod sursa(job #530096)
#include <cstdio>
#include <string>
using namespace std;
#define MAXN 2000001
#define MAX_MATCHES 1001
#define PRIME_MULT 73
#define PRIME_MOD 100007
char A[MAXN], B[MAXN];
int lenA, lenB, matches, indices[MAX_MATCHES];
void countIfMatch(int startB) {
for (int i=0;i<lenA;i++) {
if (A[i]!=B[startB+i]) {
return;
}
}
if (++matches<MAX_MATCHES) {
indices[matches] = startB;
}
}
int main()
{
int hashA, hashB, pow;
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
scanf("%s %s", A, B);
lenA = strlen(A); lenB = strlen(B);
if (lenA > lenB) {
printf("0\n");
return 0;
}
hashA = A[0]%PRIME_MOD; hashB = B[0]%PRIME_MOD; pow = 1;
for (int i = 1; i < lenA; i++) {
hashA = (hashA * PRIME_MULT + A[i]) % PRIME_MOD;
hashB = (hashB * PRIME_MULT + B[i]) % PRIME_MOD;
pow = (pow*PRIME_MULT) % PRIME_MOD;
}
if (hashA == hashB) {
countIfMatch(0);
}
for (int i = lenA; i < lenB; i++)
{
hashB = ((hashB - (B[i - lenA] * pow) % PRIME_MOD + PRIME_MOD) * PRIME_MULT + B[i]) % PRIME_MOD;
if (hashA == hashB) countIfMatch(i-lenA+1);
}
printf("%d\n", matches);
for (int i=1;i<=matches;i++) {
printf("%d ",indices[i]);
}
printf("\n");
return 0;
}