Pagini recente » Cod sursa (job #1446750) | Cod sursa (job #2648131) | Cod sursa (job #3156787) | Cod sursa (job #1544828) | Cod sursa (job #410280)
Cod sursa(job #410280)
#include <fstream>
#include <string.h>
using namespace std;
const long size=2000010;
char a[size],b[size];
long pi[size],n,m,sol[1010],l,q,i;
int prefix()
{
q=0;
pi[1]=0;
for(i=2;i<=n;++i)
{
while(q && a[q+1]!=a[i]) q=pi[q];
if(a[q+1]==a[i]) ++q;
pi[i]=q;
}
return 0;
}
int kmp()
{
l=0;
q=0;
for(i=1;i<=m;++i)
{
while(q && a[q+1]!=b[i]) q=pi[q];
if(a[q+1]==b[i]) ++q;
if(q==n)
{
++l;
if(l<=1000) sol[l]=i-n;
q=pi[q];
}
}
return 0;
}
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in >> a+1;
in >> b+1;
a[0]=' ';
b[0]=' ';
n=strlen(a)-1;
m=strlen(b)-1;
prefix();
kmp();
out << l << endl;
for(i=1;(i<=l && i<=1000);++i) out << sol[i] << " ";
in.close();
out.close();
return 0;
}