Pagini recente » Cod sursa (job #1480356) | Cod sursa (job #2214819) | Atasamentele paginii Clasament becreative23 | Cod sursa (job #1656164) | Cod sursa (job #596660)
Cod sursa(job #596660)
/*
* strmatch.c
*
* Created on: Jun 17, 2011
* Author: mihai
*/
#include <stdio.h>
#define MAX 2000002
#define min(a, b) ((a < b) ? a : b)
char A[MAX], B[MAX], pi[MAX];
int Asize, Bsize, poz[1002];
void make_prefix() {
int k = 0, q;
pi[1] = 0;
for (q = 2; q <= Asize; q++) {
while (k > 0 && A[k + 1] != A[q])
k = pi[k];
if (A[k + 1] == A[q])
++k;
pi[q] = k;
}
}
int main() {
int q = 0, i, aparitii = 0;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", A);
scanf("%s", B);
while ((A[Asize] >= 'A' && A[Asize] <= 'Z') || (A[Asize] >= 'a' && A[Asize] <= 'z') || (A[Asize] >= '0' && A[Asize] <= '9'))
++Asize;
while ((B[Bsize] >= 'A' && B[Bsize] <= 'Z') || (B[Bsize] >= 'a' && B[Bsize] <= 'z') || (B[Bsize] >= '0' && B[Bsize] <= '9'))
++Bsize;
for (i = Asize; i; i--)
A[i] = A[i - 1];
A[0] = ' ';
for (i = Bsize; i; i--)
B[i] = B[i - 1];
B[0] = ' ';
make_prefix();
for (i = 1; i <= Bsize; i++) {
while (q && A[q + 1] != B[i])
q = pi[q];
if (A[q + 1] == B[i])
++q;
if (q == Asize) {
q = pi[q];
++aparitii;
if (aparitii <= 1000)
poz[aparitii] = i - Asize;
}
}
printf("%d\n", aparitii);
for (i = 1; i <= min(1000, aparitii); i++) {
printf("%d ", poz[i]);
}
printf("\n");
return 0;
}