Pagini recente » Statistici George Ghita (eau222) | Cod sursa (job #2143556) | Cod sursa (job #1576790) | Cod sursa (job #147218) | Cod sursa (job #502479)
Cod sursa(job #502479)
# include <fstream.h>
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
int c[2000],n,m,i,q,p[2000005];
char a[2000005],b[2000005];
void prefix ()
{
int k=-1;
p[0]=k;
for (i=1;i<n;i++)
{
while (k>-1 && a[k+1]!=a[i])
k=p[k];
if (a[k+1]==a[i])
k++;
p[i]=k;
}
}
void kmp ()
{
int k=-1;
for (i=0;i<m;i++)
{
while (k>-1 && a[k+1]!=b[i])
k=p[k];
if (a[k+1]==b[i])
k++;
if (k+1==n)
{
q++;
if (q<=1000)
c[q]=i-n+1;
}
}
}
int main ()
{
f.getline (a,2000003);
f.getline (b,2000003);
n=strlen (a);
m=strlen (b);
prefix ();
kmp ();
g<<q<<"\n";
for (i=1;i<=q && i<=1000;i++)
g<<c[i]<<" ";
return 0;
}