Pagini recente » Cod sursa (job #604023) | Cod sursa (job #2416825) | Cod sursa (job #429982) | Cod sursa (job #2525437) | Cod sursa (job #587562)
Cod sursa(job #587562)
# include <fstream>
# include <iostream>
# include <cstring>
# define DIM 2000003
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<=np;++i)
printf("%d ", v[i]);
return 0;
}