Pagini recente » Cod sursa (job #362743) | Istoria paginii runda/vvvvvv | Cod sursa (job #708049) | Istoria paginii runda/ss/clasament | Cod sursa (job #544025)
Cod sursa(job #544025)
#include <stdio.h>
#include <string.h>
int n,m,v[2000002],s[1001],sol;
char a[2000002],b[2000002];
void read()
{
freopen("strmatch.in","r",stdin);
a[0]=' ';fgets(a+1,2000020,stdin);n=strlen(a)-2;
b[0]=' ';fgets(b+1,2000020,stdin);m=strlen(b)-2;
}
void prefix()
{
int i,p=0;
for (i=2;i<=n;++i)
{
while (p&&(a[i]!=a[p+1])) p=v[p];
if (a[i]==a[p+1])
{
++p;
v[i]=p;
}
}
}
void kmp()
{
int i,p=0;
for (i=1;i<=m;++i)
{
while (p&&(b[i]!=a[p+1])) p=v[p];
if (b[i]==a[p+1])
{
++p;
if (p==n)
{
++sol;
if (sol<1001) s[sol]=i-p;
}
}
}
}
void write()
{
int i;
freopen("strmatch.out","w",stdout);
printf("%d\n",sol);
if (sol>1000) sol=1000;
for (i=1;i<=sol;++i) printf("%d ",s[i]);
}
int main()
{
read();
prefix();
kmp();
write();
return 0;
}