Pagini recente » Cod sursa (job #1970139) | Cod sursa (job #2033748) | Cod sursa (job #1105576) | Cod sursa (job #1010688) | Cod sursa (job #162489)
Cod sursa(job #162489)
#include <stdio.h>
#include <string.h>
int n, m, pi[2000005], poz[1024];
char a[2000005], b[2000005];
inline int minim(int x, int y) {return x < y ? x : y;}
void citire()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(a,2000005,stdin); n = strlen(a) - 1;
fgets(b,2000005,stdin); m = strlen(b) - 1;
int i;
for (i = n; i >= 1; i--) a[i] = a[i - 1]; a[0] = ' ';
for (i = m; i >= 1; i--) b[i] = b[i - 1]; b[0] = ' ';
}
void prefix()
{
int i, q = 0;
for (i = 2, pi[1] = 0; i <= n; i++)
{
while (q && a[q + 1] != a[i]) q = pi[q];
if (a[q+1] == a[i]) q++;
pi[i] = q;
}
}
int main()
{
int i, q = 0, nr;
citire();
prefix();
for (i = 2; i <= m; i++)
{
while (q && a[q + 1] != b[i]) q = pi[q];
if (a[q + 1] == b[i]) q++;
if (q == n)
{
q = pi[n];
nr++;
if (nr <= 1000) poz[nr] = i - n;
}
}
printf("%d\n",nr);
for (i = 1; i <= minim(nr,1000); i++) printf("%d ",poz[i]);
printf("\n");
return 0;
}