Pagini recente » Istoria paginii runda/simulare-cartita-02/clasament | Istoria paginii runda/i/clasament | Cod sursa (job #1839204) | Cod sursa (job #2092740) | Cod sursa (job #200086)
Cod sursa(job #200086)
#include <cstdio>
#include <cstring>
#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define NMAX 2000010
char A[NMAX], B[NMAX];
long n,m;
long pi[NMAX],i,k;
long V[NMAX];
long nr;
int main()
{
freopen(FIN,"rt",stdin);
freopen(FOUT,"wt",stdout);
scanf("%s\n%s\n", A+1, B+1);
n=strlen(A+1);
m=strlen(B+1);
//prefix
pi[1]=0;
k=0;
for (i=2;i<=n;++i)
{
while (k>0 && A[i]!=A[k+1])
k=pi[k];
if (A[i]==A[k+1]) ++k;
pi[i]=k;
}
//KMP
k=0;
for (i=1; i<=m; ++i) {
while (A[k+1]!=B[i] && k>0) k=pi[k];
if (A[k+1]==B[i])
++k;
if (k==n)
{
++nr;
if (nr<=1000)
V[nr]=i-n;
}
}
printf("%ld\n",nr);
for (i=1; i<=nr;++i)
printf("%ld ",V[i]);
return 0;
}