Pagini recente » Cod sursa (job #3265014) | Cod sursa (job #1840559) | Cod sursa (job #1125607) | Cod sursa (job #3260293) | Cod sursa (job #143902)
Cod sursa(job #143902)
#include <stdio.h>
#include <string.h>
#define Nmax 2000005
#define min(a, b) ((a < b) ? a : b)
char P[Nmax], S[Nmax];
int c[1024], pi[Nmax], i, j, n, m, nr;
int main()
{
freopen("strmatch.in", "r", stdin);
scanf("%s\n%s", &P, &S);
fclose(stdin);
for (i=0, pi[0]=-1, j=-1, m=strlen(P); i<m; i++, pi[i]=++j)
while (j>=0 && P[i]!=P[j])
j=pi[j];
for (i=0, j=0, n=strlen(S); i<=n; i++)
{
while (P[j] !=S[i] && j) j=pi[j];
if (P[j]==S[i]) j++;
if (j==m)
{
//if (nr<1000) c[++nr]=i-m+1;
//if (nr==1000) break;
j=pi[j];
++nr;
if (nr <= 1000)
c[nr] = i-m+1;
}
}
freopen("strmatch.out", "w", stdout);
printf("%d\n", nr);
for (i=1; i<=min(nr, 1000); ++i)
printf("%d ", c[i]);
printf("\n");
fclose(stdout);
return 0;
}