Pagini recente » Cod sursa (job #2642965) | Cod sursa (job #2369838) | Cod sursa (job #1314309) | Cod sursa (job #1508437) | Cod sursa (job #587565)
Cod sursa(job #587565)
# include <fstream>
# include <iostream>
# include <cstring>
# define DIM 2000003
# define min(a,b) (a<b?a:b)
using namespace std;
int np, v[DIM], t[DIM], ls, lw;
char s[DIM], w[DIM];
void read ()
{
ifstream fin ("strmatch.in");
fin.getline(w,DIM);
fin.getline(s,DIM);
ls=strlen(s);
lw=strlen(w);
}
void calc ()
{
int p=0;
t[0]=-1;t[1]=0;
for(int i=2;i<lw;)
if (w[i-1]==w[p])
++p, t[i]=p, ++i;
else if (p)
p=t[p];
else
t[i]=0, ++i;
}
void KMP ()
{
calc();
int i=0;
for(int m=0;m<ls;)
if (s[m+i]==w[i])
{
if (i+1==lw)
{
v[++np]=m;
m+=i-t[i];
if (t[i]>-1)i=t[i];
else i=0;
}
else
++i;
}
else
{
m+=i-t[i];
if (t[i]>-1)i=t[i];
else i=0;
}
}
int main()
{
read ();
KMP();
freopen("strmatch.out", "w", stdout);
printf("%d\n", np);
for(int i=1;i<=min(1000,np);++i)
printf("%d ", v[i]);
return 0;
}