Pagini recente » Cod sursa (job #1835708) | Cod sursa (job #2934718) | Cod sursa (job #2968589) | Cod sursa (job #2880929) | Cod sursa (job #1106427)
#include <cstdio>
const int LMAX = 2000000, MAXNRREZ = 1000;
int rez [MAXNRREZ + 1];
int prefix [LMAX + 1];
char sC [LMAX + 1];
char s [LMAX + 1];
int nrRez, m, n;
int min2 (int a, int b)
{
if (a < b)
return a;
return b;
}
void setPrefix ()
{
int i, q = 0;
for (i = 2; i <= m; i ++)
{
while (q != 0 && sC [q + 1] != sC [i])
q = prefix [q];
if (sC [q + 1] == sC [i])
q ++;
prefix [i] = q;
}
}
void shift ()
{
int i;
for (i = n; i > 0; i --)
s [i] = s [i - 1];
for (i = m; i > 0; i --)
sC[i] = sC [i - 1];
sC [0] = s [0] = ' ';
}
int lungime (char s [LMAX])
{
int i = 0;
while (s [i] != NULL)
i ++;
return i;
}
void init ()
{
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w", stdout);
gets (sC);
gets (s);
n = lungime (s);
m = lungime (sC);
shift ();
setPrefix ();
}
void rezolva ()
{
int i, q = 0;
for (i = 1; i <= n; ++i)
{
while (q && sC [q + 1] != s [i])
q = prefix [q];
if (sC [q + 1] == s [i])
q ++;
if (q == m)
{
q = prefix [m];
nrRez ++;
if (nrRez <= 1000)
rez [ nrRez] = i - m;
}
}
}
void afisare ()
{
int i, min = MAXNRREZ;
printf("%d\n", nrRez);
if (nrRez < min)
min = nrRez;
for (i = 1; i <= min; i ++)
printf ("%d ", rez[i]);
}
int main ()
{
init ();
rezolva ();
afisare ();
return 0;
}