Pagini recente » Cod sursa (job #2951826) | Cod sursa (job #2191716) | Cod sursa (job #1285823) | Cod sursa (job #1545216) | Cod sursa (job #897332)
Cod sursa(job #897332)
#include <cstdio>
#include <cstring>
#define NMAX 2000001
int N, M, Rez, i, ind;
char A[NMAX], B[NMAX];
int Pi[NMAX];
int Pos[1001];
void prefix()
{
Pi[1] = ind = 0;
for( i = 2; i <= N; ++i )
{
while( ind && A[ind + 1] != A[i] )
ind = Pi[ind];
if( A[ind + 1] == A[i] )
++ind;
Pi[i] = ind;
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets( A + 1 ); N = strlen( A + 1 );
gets( B + 1 ); M = strlen( B + 1 );
prefix();
ind = 0; Rez = 0;
for( i = 1; i <= M; ++i )
{
while( ind && A[ind + 1] != B[i] )
ind = Pi[ind];
if( A[ind + 1] == B[i] )
++ind;
if( ind == N )
{
++Rez;
if( Rez <= 1000 )
Pos[Rez] = i - N + 1;
}
}
printf("%d\n", Rez);
if( Rez > 1000 )
Rez = 1000;
for( i = 1; i <= Rez; ++i )
printf("%d ", Pos[i] - 1);
printf("\n");
return 0;
}