Pagini recente » Cod sursa (job #651004) | Cod sursa (job #13430) | Cod sursa (job #1622124) | Cod sursa (job #771442) | Cod sursa (job #144376)
Cod sursa(job #144376)
#include <stdio.h>
#include <string.h>
#define mx 2000010
long i,h,n,m,p;
long pi[mx+1];
long v[1024];
char s1[mx+2],s2[mx+2];
void prefix()
{
pi[0]=0;
p=0;
for (i=2; i<=n; i++)
{
while (p>0 && s1[i]!=s1[p+1])
p=pi[p];
if (s1[i]==s1[p+1])
p++;
pi[i]=p;
}
}
void kmp()
{
n=strlen(s1+1)-1;
m=strlen(s2+1)-1;
prefix();
p=0;
h=0;
for (i=1; i<=m; i++)
{
while (p>0 && s2[i]!=s1[p+1])
p=pi[p];
if (s2[i]==s1[p+1])
p++;
if (p==n)
{
h++;
p=pi[p];
if (h<=1000)
v[h]=i-n;
}
}
}
int main(void)
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(s1+1,mx,stdin);
fgets(s2+1,mx,stdin);
kmp();
printf("%ld\n",h);
if (h>1000)
h=1000;
for (i=1; i<=h; i++)
printf("%ld ",v[i]);
fclose(stdin);
fclose(stdout);
return 0;
}