Pagini recente » Cod sursa (job #945777) | Cod sursa (job #631581) | Cod sursa (job #1671652) | Cod sursa (job #1412990) | Cod sursa (job #541980)
Cod sursa(job #541980)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define MAX 2000001
#define P1 100007
#define P2 100003
#define Size 63
int L, R1, R2, H[MAX];
char A[MAX], B[MAX];
inline char cod(char X)
{
if (X >= '0' && X <= '9')
return 1 + X - '0';
if (X >= 'a' && X <= 'z')
return 11 + X - 'a';
return 37 + X - 'A';
}
int main()
{
int i, x1, x2, y1, y2;
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
scanf("%s%s", &B, &A);
L = strlen(B);
for (i = R1 = R2 = 1; i < L; ++ i)
{
R1 = (R1 * Size) % P1;
R2 = (R2 * Size) % P2;
}
for (i = y1 = y2 = 0; i < L; ++ i)
{
y1 = (y1 * Size + cod(B[i])) % P1;
y2 = (y2 * Size + cod(B[i])) % P2;
}
for (i = x1 = x2 = 0; A[i]; ++ i)
{
if (i >= L)
{
x1 = (P1 + x1 - (cod(A[i - L]) * R1) % P1) % P1;
x2 = (P2 + x2 - (cod(A[i - L]) * R2) % P2) % P2;
}
x1 = (x1 * Size + cod(A[i])) % P1;
x2 = (x2 * Size + cod(A[i])) % P2;
if (i >= L - 1 && x1 == y1 && x2 == y2)
H[++H[0]] = i - L + 1;
}
printf("%d\n", H[0]);
for (i = 1; i <= H[0] & i < 1000; ++ i)
printf("%d ", H[i]);
printf("\n");
}