Pagini recente » Borderou de evaluare (job #2862289) | Borderou de evaluare (job #2988275) | Borderou de evaluare (job #567846) | Borderou de evaluare (job #1522377) | Cod sursa (job #640389)
Cod sursa(job #640389)
#include <stdio.h>
#define maxlen 2000002
//#define MIN(A, B) ((A) < (B)) ? (A) : (B)
char A[maxlen], B[maxlen];
int pi[maxlen], m, n;
void prefix() {
int k = 0;
pi[1] = 0;
int i;
for (i = 2; i <= m; i++) {
while (k && A[k + 1] != A[i])
k = pi[k];
if (A[k + 1] == A[i])
k = k + 1;
pi[i] = k;
}
}
int main() {
freopen("strmatch.in", "r", stdin);
fgets(A, maxlen, stdin);
fgets(B, maxlen, stdin);
for (; (A[m] >= 'A' && A[m] <= 'Z') || (A[m] >= 'a' && A[m] <= 'z')
|| (A[m] >= '0' && A[m] <= '9'); ++m);
for (; (B[n] >= 'A' && B[n] <= 'Z') || (B[n] >= 'a' && B[n] <= 'z')
|| (B[n] >= '0' && B[n] <= '9'); ++n);
int i;
for (i = m; i > 0; i--)
A[i] = A[i - 1];
A[0] = ' ';
for (i = n; i > 0; i--)
B[i] = B[i - 1];
B[0] = ' ';
prefix();
int q = 0, j = 0, ans[1024];
for (i = 0; i < n; i++) {
while (q && A[q + 1] != B[i])
q = pi[q];
if (A[q + 1] == B[i])
q++;
if (q == m) {
q = pi[m];
j++;
if (j <= 1000)
ans[j - 1] = i - m;
}
}
freopen("strmatch.out", "w", stdout);
printf("%d\n", j);
int min = (j < 1000) ? j : 1000;
for (i = 0; i < min; i++)
printf("%d ", ans[i]);
printf("\n");
return 0;
}