Pagini recente » Cod sursa (job #1898745) | Cod sursa (job #138048) | Cod sursa (job #738853) | Cod sursa (job #664095) | Cod sursa (job #1479958)
#include <stdio.h>
#include <string.h>
#define minim(a, b) ((a < b) ? a : b)
#define MAX 2000005
int lungime_subsir, lungime_sir;
char subsir[MAX], sir[MAX];
int pi[MAX], pozitie[1024];
void make_prefix()
{
int i, q = 0;
for (i = 2, pi[1] = 0; i <= lungime_subsir; i++){
while (q && subsir[q+1] != subsir[i]){
q = pi[q];
}
if (subsir[q+1] == subsir[i]){
q++;
}
pi[i] = q;
}
}
int main(void)
{
int i, q = 0, nr_aparitii = 0;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(subsir, sizeof(subsir), stdin);
fgets(sir, sizeof(sir), stdin);
lungime_subsir=strlen(subsir)-1;
lungime_sir=strlen(sir)-1;
for (i = lungime_subsir; i; i--){
subsir[i] = subsir[i-1];
}
subsir[0] = ' ';
for (i = lungime_sir; i; i--){
sir[i] = sir[i-1];
}
sir[0] = ' ';
make_prefix();
for (i = 1; i <= lungime_sir; i++){
while (q && subsir[q+1] != sir[i]){
q = pi[q];
}
if (subsir[q+1] == sir[i]){
q++;
}
if (q == lungime_subsir){
q = pi[lungime_subsir];
nr_aparitii++;
if (nr_aparitii <= 1000){
pozitie[nr_aparitii] = i-lungime_subsir;
}
}
}
printf("%d\n", nr_aparitii);
for (i = 1; i <= minim(nr_aparitii, 1000); i++){
printf("%d ", pozitie[i]);
}
printf("\n");
fclose(stdin);
fclose(stdout);
return 0;
}