Pagini recente » Cod sursa (job #257655) | Cod sursa (job #647257) | Cod sursa (job #2990808) | Cod sursa (job #1365653) | Cod sursa (job #390335)
Cod sursa(job #390335)
#include <cstdio>
#include <cstring>
#define DIM 2000005
int T[DIM], L1, L2, count, sol[1001];
char S[DIM], W[DIM];
void KMP()
{
T[0] = -1;
T[1] = 0;
int pos = 2, cnd = 0;
while (pos < L1)
if (W[pos - 1] == W[cnd])
T[pos] = ++cnd, ++pos;
else
if (cnd > 0)
cnd = T[cnd];
else
T[pos] = 0, ++pos;
int m = 0, i = 0;
while (m + i < L2)
if (W[i] == S[m + i])
{
++i;
if (i == L1)
{
++count;
if (count <= 1000)
sol[count] = m;
}
}
else
{
m += i - T[i];
if (T[i] > -1)
i = T[i];
else
i = 0;
}
}
int main()
{
FILE *f = fopen("strmatch.in", "r");
fscanf(f, "%s%s", W, S);
fclose(f);
L1 = strlen(W);
L2 = strlen(S);
KMP();
f = fopen("strmatch.out", "w");
fprintf (f, "%d\n", count);
for (int i = 1; i <= ((count>1000)?1000:count); ++i)
fprintf (f, "%d ", sol[i]);
fclose(f);
return 0;
}