Pagini recente » Cod sursa (job #1249053) | Cod sursa (job #962402) | Cod sursa (job #1063954) | Cod sursa (job #1931516) | Cod sursa (job #401260)
Cod sursa(job #401260)
//#include <stdio.h>
#include <fstream>
using namespace std;
const long size=2000010;
char a[size],b[size];
long pi[size],n,m,sol[size],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)
{
sol[++l]=i-n;
q=pi[q];
}
}
return 0;
}
int main()
{
// freopen("strmatch.in","r",stdin);
// freopen("strmatch.out","w",stdout);
ifstream in("strmatch.in");
ofstream out("strmatch.out");
// gets(a);
// gets(b);
in >> a;
in >> b;
for(n=0;(a[n]>='a'&&a[n]<='z')||(a[n]>='A'&&a[n]<='Z')||(a[n]>='0'&&a[n]<='9');++n);
for(m=0;(b[n]>='a'&&b[m]<='z')||(b[m]>='A'&&b[m]<='Z')||(b[m]>='0'&&b[m]<='9');++m);
for(i=n;i;--i) a[i]=a[i-1]; a[0]=' ';
for(i=m;i;--i) b[i]=b[i-1]; b[0]=' ';
prefix();
kmp();
// printf("%ld\n",l);
// for(i=1;i<=l;++i) printf("%ld ",sol[i]);
out << l << endl;
for(i=1;i<=l;++i) out << sol[i] << " ";
in.close();
out.close();
return 0;
}