Pagini recente » Cod sursa (job #2543236) | Cod sursa (job #1015516) | Cod sursa (job #3227363) | Cod sursa (job #239955) | Cod sursa (job #570994)
Cod sursa(job #570994)
#include<string.h>
#include<stdio.h>
char s[2000002],a[2000002];
int p[2000003];
int d[2000003];
int n,m;
int nr=0;
void calculprefix()
{
int k = 0;
p[1] = 0;
for(int i=2;i<n;i++)
{k=p[i-1];
while(k > 0 && s[k + 1]!=s[i])
k = p[k];
if(s[k + 1] == s[i])
k = k + 1;
p[i] = k;
}
}
void kmp()
{
int k=0;
for(int i=1;i<m&&nr<1000;i++)
{
while(k > 0 && s[k + 1]!=a[i])
k = p[k];
if(s[k + 1] == a[i])
k = k + 1;
if(k==n-1)
{ nr++;
d[nr]=i-n+1;
} k=p[k];
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(s+1,2000002,stdin);
fgets(a+1,2000002,stdin);
n = strlen(s+1);
m = strlen(a+1);
calculprefix();
kmp();
printf("%d",nr);
for(int i=1;i<=nr;i++)
printf("%d ",d[i]);
return 0;
}