Pagini recente » Cod sursa (job #881212) | Cod sursa (job #2749947) | Cod sursa (job #780356) | Cod sursa (job #2549004) | Cod sursa (job #303899)
Cod sursa(job #303899)
#include <cstdio>
#include <cstring>
using namespace std;
#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define Nmax 2001000
#define Nmin 1001
char a[Nmax];
char b[Nmax];
int pi[Nmax];
int sir[Nmin];
int n,m,nr;
inline void citire()
{
int i,j;
freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%s\n", a+1);
scanf("%s\n", b+1);
n=strlen(a+1);
m=strlen(b+1);
}
inline void prefix()
{
int i,j,k;
k=0;
pi[1]=0;
for (i=2;i<=n;++i)
{
while(k>0 && a[i]!=a[k+1])
k=pi[k];
if (a[i]==a[k+1])
k++;
pi[i]=k;
}
}
inline void kmp()
{
int i,j,k;
k=0;
nr=0;
for (i=1;i<=m;++i)
{
while(k>0 && b[i]!=a[k+1])
k=pi[k];
if (b[i]==a[k+1])
k++;
if (k==n)
{
nr++;
if (sir[0]<1000)
{
sir[++sir[0]]=i-n;
}
else
++sir[0];
}
}
}
inline void scrie()
{
int i;
prefix();
kmp();
printf("%d\n", nr);
for (i=1;i<=sir[0];++i)
printf("%d ", sir[i]);
}
int main()
{
citire();
scrie();
fclose(stdin);
fclose(stdout);
return 0;
}