Pagini recente » Istoria paginii utilizator/suty | Profil denis__vladu | Profil Ubb_Lili | Profil Pinciu | Cod sursa (job #172040)
Cod sursa(job #172040)
#include<stdio.h>
#include<string.h>
#define N 2000002
char a[N],b[N];
int n,m,pi[N],nr,poz[N];
void prefix()
{
int i,k;
pi[1]=0;
k=0;
for(i=2;i<=n;i++)
{
while(k>0&&a[k+1]!=a[i])
k=pi[k];
if(a[k+1]==a[i])
k++;
pi[i]=k;
}
}
void kmp()
{
int i,q;
q=0;
for(i=1;i<=m;i++)
{
while(q>0&&a[q+1]!=b[i])
q=pi[q];
if(a[q+1]==b[i])
q++;
if(q==n)
poz[++nr]=i-n+1;
}
}
void afis()
{
int i;
printf("%d\n",nr);
for(i=1;i<=nr;i++)
printf("%d ",poz[i]-1);
}
void solve()
{
scanf("%s\n",a+1);
n=strlen(a+1);
scanf("%s",b+1);
m=strlen(b+1);
prefix();
kmp();
afis();
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
solve();
return 0;
}