Pagini recente » Cod sursa (job #2298154) | Cod sursa (job #1426751) | Cod sursa (job #402614) | Cod sursa (job #3244134) | Cod sursa (job #169906)
Cod sursa(job #169906)
#include <stdio.h>
#include <string.h>
#define K 2000009
#define lmax 1000
char A[K],B[K];
int pi[K],poz[lmax+1];
int M,N;
inline int minim(int x,int y){
if(x<y)
return x;
return y;
}
void scan()
{
freopen("strmatch.in", "r",stdin);
freopen("strmatch.out", "w",stdout);
gets(A+1); gets(B+1);
M=strlen(A+1); N=strlen(B+1);
}
void make_prefix()
{
int i,q=0;
for(pi[1]=0,i=2 ;i<= M ;++i)
{
while ( q && A[q+1]!=A[i] )
q = pi[q];
if (A[q+1] == A[i])
++q;
pi[i]=q;
}
}
void solve()
{
int n=0,q=0;
make_prefix();
for(int i=1;i<=N;++i)
{
while( q && A[q+1]!=B[i] )
q=pi[q];
if (A[q+1]==B[i])
++q;
if ( q==M )
{
q=pi[M];
++n;
if (n<=lmax)
poz[n]=i-M;
}
}
printf("%d\n", n);
for(int i=1;i<=minim(n,lmax);++i)
printf("%d ", poz[i]);
}
int main()
{
scan();
solve();
return 0;
}