Pagini recente » Cod sursa (job #69461) | Cod sursa (job #2054942) | Cod sursa (job #2273982) | Cod sursa (job #1857008) | Cod sursa (job #184170)
Cod sursa(job #184170)
#include<stdio.h>
#include<string.h>
#define MAXN 2000001
int m,i,n,nrsol;
int p[MAXN],sol[1001];
char s1[MAXN],s2[MAXN];
void prefix()
{
int k=0,i;
for(i=2;i<=m;i++)
{
while(k>0&&s2[k+1]!=s2[i])
k=p[k];
if(s2[k+1]==s2[i])
k++;
p[i]=k;
}
}
void kmp()
{
int i,k=0;
for(i=1;i<=n;i++)
{
while(k>0&&s2[k+1]!=s1[i])
k=p[k];
if(s2[k+1]==s1[i])
k++;
if(k==m)
{
nrsol++;
if(nrsol<=100)
sol[nrsol]=i-m;
k=p[m];
}
}
}
int main(void)
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",s2+1,s1+1);
s1[0]=' ';
s2[0]=' ';
m=strlen(s2);
m--;
n=strlen(s1);
n--;
prefix();kmp();
printf("%d\n",nrsol);
for(i=1;i<=nrsol&&i<=1000;i++)
printf("%d ",sol[i]);
return 0;
}