Pagini recente » Cod sursa (job #2956386) | Cod sursa (job #505949) | Cod sursa (job #1063403) | Cod sursa (job #2146261) | Cod sursa (job #169914)
Cod sursa(job #169914)
#include <stdio.h>
#include <string.h>
#define K 2000009
char A[K],B[K];
int pi[K],poz[1001];
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<=1000) poz[n]=i-M;
}
}
printf("%d\n", n);
for(int i=1;i<=minim(n,1000);++i)
printf("%d ", poz[i]);
}
int main()
{
scan();
solve();
return 0;
}