Pagini recente » Cod sursa (job #1045827) | Cod sursa (job #693991) | Cod sursa (job #1941208) | Cod sursa (job #1026803) | Cod sursa (job #337812)
Cod sursa(job #337812)
#include <stdio.h>
#define pmax 2000000
char A [pmax+5], B [pmax+5];
int n, m, nrs, pos [1005], pi [pmax+5];
void scan ()
{
gets (A+1);
gets (B+1);
for (n=1; A [n]; ++n);
for (m=1; B [m]; ++m); //fprintf(stderr, "n=%d m=%d\n", n, m);
}
void form_pi ()
{
int i, q=0;
pi [1]=0;
for (i=2; i <= n; ++i)
{
while (q && (A [q+1] != A [i]))
q=pi [q];
if (A [q+1] == A [i])
++q;
pi [i]=q;
}
}
void kmp ()
{
int i, q=0;
for (i=1; i <= m; ++i)
{
while (q && (A [q+1] != B [i]))
q=pi [q];
if (A [q+1] == B [i])
++q;
if (q == n-1)
{
q=pi [n-1];
++nrs;
if (nrs <= 1000)
pos [nrs]=i-n+1;
}
}
}
void print ()
{
int i, k=(nrs < 1000)? nrs:1000;
printf ("%d\n", nrs);
for (i=1; i <= k; ++i)
printf ("%d ", pos [i]);
printf ("\n");
}
int main ()
{
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w", stdout);
scan ();
form_pi ();
kmp ();
print ();
return 0;
}