Pagini recente » Cod sursa (job #603536) | Cod sursa (job #2349843) | Cod sursa (job #1080520) | Cod sursa (job #1745582) | Cod sursa (job #1000188)
# include <iostream>
# include <fstream>
FILE *f = fopen("strmatch.in","r");
FILE *g = fopen("strmatch.out","w");
#define MAX 2000005
#define MAXM 1000
#define isChar(a) (('a' <= (a) && (a) <= 'z') || ('A' <= (a) && (a) <= 'Z') || '0' <= (a) && (a) <= '9')
#define min(a,b) (((a) < (b)) ? (a) : (b))
char A[MAX], B[MAX];
int pi[MAX], n = 1, m = 1, match[MAXM], nrm = 0;
void build_prefix()
{
pi[1] = 0;
for (int q = 2, k = 0; q <= m; q++) {
while (k && A[k + 1] != A[q]) {
k = pi[k];
}
if (A[k + 1] == A[q]) {
k++;
}
pi[q] = k;
}
}
void kmp()
{
for (int i = 1, q = 0; i <= n; i++) {
while (q && A[q + 1] != B[i]) {
q = pi[q];
}
if (A[q + 1] == B[i]) {
q++;
}
if (q == m) {
nrm++;
if (nrm <= MAXM) {
match[nrm - 1] = i - m;
}
q = pi[q];
}
}
}
int main()
{
A[0] = B[0] = ' ';
fgets(A + 1, MAX, f);
fgets(B + 1, MAX, f);
while (isChar(A[m])) {
m++;
}
while (isChar(B[n])) {
n++;
}
n--, m--;
build_prefix();
kmp();
fprintf(g, "%d\n", nrm);
for (int i = 0; i < min(nrm, MAXM); i++) {
fprintf(g, "%d ", match[i]);
}
fclose(f);
fclose(g);
return 0;
}