Pagini recente » Cod sursa (job #2918869) | Cod sursa (job #1555828) | Cod sursa (job #177968) | Cod sursa (job #2488760) | Cod sursa (job #1377138)
#include <cstdio>
#include <cstring>
#include <algorithm>
#define NMAX 2000005
using namespace std;
int T[NMAX], nrap, afis[NMAX], lA, lB;
char A[NMAX], B[NMAX];
void citire()
{
A[0] = B[0] = '#';
scanf("%s", A + 1);
scanf("%s", B + 1);
lA = strlen(A) - 1;
lB = strlen(B) - 1;
}
void prefix()
{
int q = 0;
for (int i = 2; i <= lA; ++i)
{
T[i] = 0;
while (q && A[i] != A[q + 1])
q = T[q];
if (A[i] == A[q + 1])
q++;
T[i] = q;
}
}
void kmp()
{
int q = 0;
for (int i = 1; i <= lB; ++i)
{
while (q && B[i] != A[q + 1])
q = T[q];
if (B[i] == A[q + 1])
q++;
if (q == lA)
{
q = T[q];
nrap++;
if (nrap <= 1000)
afis[nrap] = i - lA;
}
}
}
void afisare()
{
int cnt = min(nrap, 1000);
printf("%d\n", nrap);
for (int i = 1; i <= cnt; ++i)
printf("%d ", afis[i]);
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
citire();
prefix();
kmp();
afisare();
return 0;
}