Pagini recente » Cod sursa (job #2931370) | Cod sursa (job #2894487) | Cod sursa (job #442770) | Cod sursa (job #2868729) | Cod sursa (job #362416)
Cod sursa(job #362416)
#include <cstdio>
#define lm 2000010
#define sm 1001
#include <cstring>
int n, m, pi[lm], r[sm];
char A[lm], B[lm];
void prefix()
{
pi[1]=0;
int i, k=0;
for (i=2; i<=m; i++)
{
while (k && A[k+1]!=A[i]) k = pi[k];
if (A[k+1]==A[i]) k++;
pi[i]=k;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",A);
scanf("%s",B);
m=strlen(A);
n=strlen(B);
int i;
for (i=m; i>0; i--) A[i]=A[i-1];
for (i=n; i>0; i--) B[i]=B[i-1];
prefix();
int k=0, s=0;
for (i=1; i<=n; i++)
{
while (k && A[k+1]!=B[i]) k=pi[k];
if (A[k+1]==B[i]) k++;
if (k==m)
{
s++;
if (s<sm) r[s]=i-m;
}
}
printf("%d\n",s);
if (s>=sm) s=sm-1;
for (i=1; i<=s; i++) printf("%d ",r[i]);
}