Pagini recente » Cod sursa (job #1482371) | Cod sursa (job #754376) | Cod sursa (job #825031) | Cod sursa (job #2969200) | Cod sursa (job #574352)
Cod sursa(job #574352)
#include <fstream>
#include <string>
using namespace std;
#define DIM 1<<21
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
int NA, NB, P[DIM], R[1001];
char A[DIM], B[DIM];
int main()
{
int i, k;
fi >> A + 1 >> B + 1;
NA = strlen(A + 1) + 1;
NB = strlen(B + 1) + 1;
k = 0;
P[1] = 0;
for (i = 2; i < NA; i++)
{
while (k > 0 && A[k+1] != A[i])
k = P[k];
if (A[k+1] == A[i])
k++;
P[i] = k;
}
k = 0;
for (i = 1; i < NB; i++)
{
while (k > 0 && A[k+1] != B[i])
k = P[k];
if (A[k+1] == B[i])
k++;
if (k == NA - 1)
{
R[++R[0]] = i - NA + 1;
if (R[0] == 1000)
break;
}
}
fo << R[0] << '\n';
for (i = 1; i <= R[0]; i++)
fo << R[i] << ' ';
return 0;
}