Pagini recente » Cod sursa (job #1669860) | Cod sursa (job #2383468) | Cod sursa (job #29521) | Cod sursa (job #1064376) | Cod sursa (job #2325746)
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <cstring>
#define minim(a, b) ((a < b) ? a : b)
#define NMax 2000005
using namespace std;
int M, N;
char A[NMax], B[NMax];
int pi[NMax], pos[1024];
ifstream in("strmatch.in");
ofstream out("strmatch.out");
void make_prefix()
{
int i, q = 0;
for (i = 1, pi[0] = 0; i < M; ++i)
{
while ((q > 0) and (A[q] != A[i]))
q = pi[q - 1];
if (A[q] == A[i])
++q;
pi[i] = q;
}
}
int main(void)
{
int i, q = 0, n = 0;
in >> A; //cout << A << '\n';
in >> B; //cout << B << '\n';
M = strlen(A);
N = strlen(B);
make_prefix();
for (i = 0; i < N; ++i)
{
while ((q > 0) and (A[q] != B[i]))
q = pi[q - 1];
if (A[q] == B[i])
++q;
if (q == M)
{
q = pi[q - 1];
++n;
if (n <= 1000)
pos[n] = i - M + 1;
}
}
out << n << '\n';
for (i = 1; i <= minim(n, 1000); ++i)
out << pos[i] << " ";
out << '\n';
return 0;
}