Pagini recente » Cod sursa (job #9424) | Cod sursa (job #1863464) | Cod sursa (job #416525) | Cod sursa (job #280984) | Cod sursa (job #793586)
Cod sursa(job #793586)
#include <cstdio>
#include <cstring>
#define lg 2000005
using namespace std;
FILE *fin=freopen("strmatch.in","r",stdin);
FILE *fout=freopen("strmatch.out","w",stdout);
char a[lg],b[lg];
int m,n,p[lg],sol[1001],k=0;
void read()
{
scanf("%s\n%s",a,b);
m=strlen(a);
n=strlen(b);
}
void prefix()
{
int i=0,j=-1;
p[i]=j;
while(i<m)
{
while(j>=0 && a[i]!=a[j])
j=p[j];
i++; j++;
p[i]=j;
}
}
void cauta()
{
int i=0,j=0;
while(i<n)
{
while(j>=0 && b[i]!=a[j])
j=p[j];
i++;
j++;
if(j==m)
{
if(k<1000)
sol[k++]=i-j;
else
k++;
j=p[j];
}
}
}
void print()
{
printf("%d\n",k);
for(int i=0; i<k && i<1000;i++)
printf("%d ", sol[i]);
}
int main()
{
read();
prefix();
cauta();
print();
return 0;
}