Pagini recente » Monitorul de evaluare | Cod sursa (job #406087) | Cod sursa (job #1870525) | Cod sursa (job #2006223) | Cod sursa (job #162316)
Cod sursa(job #162316)
#include <cstdio>
#include <cstring>
#define DIM 2000002
using namespace std;
char A[DIM], B[DIM];
int N, M, pi[DIM], poz[1024], sol;
void Prefix()
{
int k = 0;
for (int i = 2; i <= M; i++)
{
while (k > 0 && A[k + 1] != A[i]) k = pi[k];
if (A[k + 1] == A[i]) k++;
pi[i] = k;
}
}
void KMP()
{
int k = 0;
for (int i = 1; i <= N; i++)
{
while (k > 0 && A[k + 1] != B[i]) k = pi[k];
if (A[k + 1] == B[i]) k++;
if (k == M)
{
sol++;
if (sol < 1000) poz[sol] = i - M;
k = pi[k];
}
}
}
int main()
{
FILE *fin = fopen("strmatch.in", "r");
FILE *fout = fopen("strmatch.out", "w");
fscanf(fin, "%s%s", &A, &B);
M = strlen(A);
N = strlen(B);
for (int i = M; i > 0; i--) A[i] = A[i - 1];
for (int j = N; j > 0; j--) B[j] = B[j - 1];
Prefix();
KMP();
fprintf(fout, "%d\n", sol);
for (int i = 1; i <= sol; i++)
fprintf(fout, "%d ", poz[i]);
return 0;
}