Pagini recente » Cod sursa (job #730373) | Cod sursa (job #2533002) | Cod sursa (job #2842068) | Cod sursa (job #1105201) | Cod sursa (job #683403)
Cod sursa(job #683403)
#include <fstream>
using namespace std;
ifstream fi ("kmp.in");
ofstream fo ("kmp.out");
const int dim = 2000005;
char A[dim], B[dim];
int P[dim], R[1005], N;
void cit ()
{
fi >> A+1 >> B+1;
}
void prf ()
{
int k = 0;
for (int i = 2; A[i] != 0; i++)
{
while (k > 0 && A[k + 1] != A[i])
k = P[k];
if (A[k + 1] == A[i])
k++;
P[i] = k;
}
}
void kmp ()
{
int k = 0;
for (int i = 1; B[i] != 0; i++)
{
while (k > 0 && A[k + 1] != B[i])
k = P[k];
if (A[k + 1] == B[i])
k++;
if (A[k + 1] == 0)
{
N++;
if (N <= 1000)
R[N] = i - k;
}
}
}
void afi ()
{
fo << N << '\n';
if (N > 1000) N = 1000;
for (int i = 1; i <= N; i++)
fo << R[i] << ' ';
}
int main ()
{
cit ();
prf ();
kmp ();
afi ();
return 0;
}