Pagini recente » Profil RoxanaaMIhaelaa | Istoria paginii utilizator/uaic_cdv_anghel_asandoaiei_bita | Cod sursa (job #2886720) | Cod sursa (job #111269) | Cod sursa (job #1747712)
//Knuth-Morris-Pratt
#include <stdio.h>
#define NMax 2000005
int m,n;
char M[NMax], N[NMax]; //Cei doi vectori
int pi[NMax]; //vectorul de prefixe
int pos[1024],p; //vectorul de pozitii
void creare_prefix()
{
int k=0;
int i;
pi[1]=0;
for (i=2;i<=n; i++)
{
while (k>0 && N[k+1]!=N[i])
k=pi[k];
if (N[k+1]==N[i])
k++;
pi[i]=k;
}
}
void potrivire()
{
int q=0;
int i;
for (i=0; i<=m; i++)
{
while (q>0 && N[q+1]!=M[i])
q=pi[q];
if (N[q+1]==M[i])
q++;
if (q==n)
{
p++;
if (p<=1000)
pos[p]=i-n;
}
}
}
int min(int p, int mmm)
{
if (p<=mmm)
return(p);
else
return(mmm);
}
void afisare()
{
printf("%d\n",p);
int i;
for (i= 1; i<=min(p,1000); i++)
printf("%d ",pos[i]);
}
int main(void)
{
int i;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(N, sizeof(N), stdin);
fgets(M, sizeof(M), stdin);
/*
TEORIE: prototype
char *fgets(char *str, int n, FILE *stream) ;
n -- This is the maximum number of characters to be read
(including the final null-character).
Usually, the length of the array passed as str is used.
*/
for (; (N[n] >= 'A' && N[n] <= 'Z') || (N[n] >= 'a' && N[n] <= 'z')
|| (N[n] >= '0' && N[n] <= '9'); ++n);
for (; (M[m] >= 'A' && M[m] <= 'Z') || (M[m] >= 'a' && M[m] <= 'z')
|| (M[m] >= '0' && M[m] <= '9'); ++m);
for (i = n; i; --i)
N[i] = N[i-1];
N[0] = ' ';
for (i = m; i; --i)
M[i] = M[i-1];
M[0] = ' ';
//KMP: creare prefix
p=0;
creare_prefix();
/*AFISARE PREFIX
for (i=1; i<=n; i++)
printf("%d ",pi[i]);
printf("\n");
*/
//KMP: ptrivire
potrivire();
afisare();
return 0;
}