Pagini recente » Cod sursa (job #173797) | Istoria paginii utilizator/catalinaionela77 | Cod sursa (job #1900204) | Cod sursa (job #358331) | Cod sursa (job #1202969)
#include <cstdio>
#include <cstring>
#define MAX 2000005
using namespace std;
char p[MAX],s[MAX];
int n,m,pi[MAX],sol[MAX],nrsol;
void prefix();
void kmp();
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int i;
scanf("%s\n%s",p+1,s+1);
kmp();
printf("%d\n",nrsol);
if(nrsol>1000)
nrsol=1000;
for(i=1;i<=nrsol;++i)
printf("%d ",sol[i]);
return 0;
}
void prefix()
{
int k;
pi[1]=0,k=0;
for(int i=2;i<=m;++i)
{
while(k>0 and p[k+1]!=p[i])
k=pi[k];
if(p[k+1]==p[i])
k++;
pi[i]=k;
}
}
void kmp()
{
int q=0;
n=strlen(s+1),m=strlen(p+1);
prefix();
for(int i=1;i<=n;++i)
{
while(q>0 and p[q+1]!=s[i])
q=pi[q];
if(p[q+1]==s[i])
q++;
if(q==m)
nrsol++,sol[nrsol]=i-q,q=pi[q];
}
}