Pagini recente » Cod sursa (job #995051) | Cod sursa (job #2086104) | Cod sursa (job #931037) | Cod sursa (job #43984) | Cod sursa (job #541915)
Cod sursa(job #541915)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define MAX 2000000
#define P 666013
#define Size 64
int L, R[MAX];
char A[MAX], B[MAX];
vector <int> H[P];
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, x;
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
gets(B);
gets(A);
L = strlen(B) - 1;
for (i = R[0] = 1; i < L; ++ i)
R[i] = (R[i - 1] * Size) % P;
for (i = x = 0; A[i]; ++ i)
{
if (i >= L)
x = (x - cod(A[i - L]) * R[L - 1]) % P;
x = (x * Size + cod(A[i])) % P;
if (i >= L - 1)
H[x % P].push_back(i - L + 1);
}
for (i = x = 0; i < L; ++ i)
x = (x * Size + cod(B[i])) % P;
printf("%d\n", H[x % P].size());
for (i = 0; i < H[x % P].size(); ++ i)
printf("%d ", H[x % P][i]);
printf("\n");
}