Pagini recente » Cod sursa (job #56339) | Cod sursa (job #1005455) | Cod sursa (job #507664) | Cod sursa (job #2589519) | Cod sursa (job #1649254)
#include<stdio.h>
using namespace std;
const int N = 2000005;
char a[N], b[N];
int pi[N], sol[N];
int na = 0, nb = 0, nrsol;
void precalc ()
{
int k = 0;
pi[0] = 0;
int q;
for (q = 1; q < na; q++)
{
while ((k != 0) && a[k] != a[q])
k = pi[k - 1];
if (a[k] == a[q])
k++;
pi[q] = k;
}
}
void gaseste ()
{
int q = 0, i;
for (i = 0; i < nb; i++)
{
while ((q != 0) && a[q] != b[i])
q = pi[q - 1];
if (a[q] == b[i])
q++;
if (q == na)
sol[++nrsol] = i - na + 1;
}
}
int main ()
{
FILE *in, *out;
in = fopen ("strmatch.in", "r");
out = fopen ("strmatch.out", "w");
char x;
x = getc (in);
while (x != '\n')
{
a[na++] = x;
x = fgetc (in);
}
x = fgetc (in);
while (x != EOF && x != '\n')
{
b[nb++] = x;
x = fgetc (in);
}
precalc();
gaseste();
fprintf (out, "%d\n", nrsol);
int i;
if (nrsol > 1000)
nrsol = 1000;
for (i = 1; i <= nrsol; i++)
fprintf (out, "%d ", sol[i]);
return 0;
}