Pagini recente » Cod sursa (job #50761) | Cod sursa (job #3726) | Cod sursa (job #2335778) | Cod sursa (job #217926) | Cod sursa (job #1105225)
#include <cstdio>
#include <cstring>
#include <algorithm>
#define Nmax 2000010
#define Pmax 1010
using namespace std;
char A[Nmax], B[Nmax];
int P[Nmax], Pos[Pmax], M, N, nr;
void Prefix()
{
int q = 0;
for (int i = 2; i <= M; ++i)
{
P[i] = 0;
while (q && A[i] != A[q + 1])
q = P[q];
if (A[q + 1] == A[i])
q++;
P[i] = q;
}
}
void Citire()
{
scanf("%s\n%s", A + 1, B + 1);
A[0] = B[0] = 'x';
M = strlen(A) - 1;
N = strlen(B) - 1;
}
void Rezolvare()
{
int q = 0;
for (int i = 1; i <= N; ++i)
{
while (q && A[q + 1] != B[i])
q = P[q];
if (A[q + 1] == B[i])
q++;
if (M == q)
{
q = P[M];
nr++;
if (nr <= 1000)
Pos[nr] = i - M;
}
}
}
void Afisare()
{
int sf = min (nr, 1000);
printf("%d\n", nr);
for (int i = 1; i <= sf; ++i)
printf("%d ", Pos[i]);
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
Citire();
Prefix();
Rezolvare();
Afisare();
return 0;
}