Pagini recente » Cod sursa (job #2838181) | Cod sursa (job #1440308) | Cod sursa (job #321193) | Cod sursa (job #1113505) | Cod sursa (job #298991)
Cod sursa(job #298991)
#include <stdio.h>
#include <string.h>
#define Nmax 101
char s1[Nmax],s2[Nmax],x[Nmax];
int pi[Nmax],Y[1001];
void cit()
{
fgets(s2+1,Nmax,stdin);
if(s2[strlen(s2+1)]=='\n')
s2[strlen(s2+1)]=NULL;
fgets(s1+1,Nmax,stdin);
if(s1[strlen(s1+1)]=='\n')
s1[strlen(s1+1)]=NULL;
}
int min(int a,int b)
{
return a<b?a:b;
}
void prefix()
{
int n=strlen(s2+1),k,i;
k=0;
pi[1]=0;
for(i=2;i<=n;i++)
{
while(k>0&&s2[k+1]!=s2[i])
k=pi[i];
if(s2[k+1]==s2[i])
k++;
pi[i]=k;
}
}
void kmp()
{
int m=strlen(s1+1),n=strlen(s2+1),q,i;
prefix();
q=0;
for(i=1;i<=m;i++)
{
while(q>0&&s2[q+1]!=s1[i])
q=pi[q];
if(s2[q+1]==s1[i])
q++;
if(q==n)
Y[++Y[0]]=i-n+1;
//printf("%d ",i-n+1);
}
}
void scr()
{
int i;
printf("%d\n",Y[0]);
for(i=1;i<=min(Y[0],1000);i++)
printf("%d ",Y[i]);
}
int main()
{
freopen("date.in","r",stdin);
freopen("date.out","w",stdout);
cit();
kmp();
scr();
return 0;
}