Pagini recente » Cod sursa (job #3036333) | Cod sursa (job #244663) | Cod sursa (job #2551626) | Cod sursa (job #3179698) | Cod sursa (job #530124)
Cod sursa(job #530124)
#include <cstdio>
#include <string>
using namespace std;
#define MAXN 2000001
#define MAX_MATCHES 1000
#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 = hashB = 0; pow = 1;
for (int i = 0; i < lenA; i++) {
hashA = (hashA * PRIME_MULT + A[i]) % PRIME_MOD;
hashB = (hashB * PRIME_MULT + B[i]) % PRIME_MOD;
if ( i!= 0)
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=0;i<matches;i++) {
printf("%d ",indices[i]);
}
printf("\n");
return 0;
}