Pagini recente » Cod sursa (job #60912) | Cod sursa (job #1687993) | Cod sursa (job #339530) | Cod sursa (job #147386) | Cod sursa (job #279312)
Cod sursa(job #279312)
#include<fstream.h>
#include<string.h>
char a[1000],b[1000];
long n,m;
long p[1000],x[1005],c;
void prefix()
{ long i;
long k=0;
for(i=2,p[1]=0;i<=n;i++)
{ while(k>0 && a[k+1]!=a[i])
k=p[k];
if(a[k+1]==a[i])
k+=1;
p[i]=k;
}
}
void kmp()
{ long i,q;
q=0;
prefix();
for(i=1;i<=m;i++)
{ while(q>0 && a[q+1]!=b[i])
q=p[q];
if(a[q+1]==b[i])
q+=1;
if(q==n)
{ c++;
q=p[n];
if(c<=1000)
x[c]=i-n;
}
}
}
int main()
{ ifstream f("strmatch.in");
long i;
f>>a;
f>>b;
n=strlen(a);
m=strlen(b);
for(i=m;i>=0;i--)
b[i]=b[i-1];
for(i=n;i>=0;i--)
a[i]=a[i-1];
a[0]=' ';
b[0]=' ';
kmp();
ofstream g("strmatch.out");
g<<c<<" \n";
if(c>1000) c=1000;
for(i=1;i<=c;i++)
g<<x[i]<<" ";
f.close();
g.close();
return 0;
}