Pagini recente » Cod sursa (job #2603258) | Cod sursa (job #256338) | Cod sursa (job #2630722) | Cod sursa (job #2439675) | Cod sursa (job #699294)
Cod sursa(job #699294)
#include <cstdio>
#include <cstring>
#define LMAX 2000005
char P[LMAX], S[LMAX];
int Pi[LMAX], Sol[LMAX], i, LgCt, LgP, LgS;
inline void Prefix()
{
for( Pi[1] = LgCt = 0, i = 2; i <= LgP; ++i )
{
for( ; P[LgCt + 1] != P[i] && LgCt; LgCt = Pi[LgCt] );
if( P[LgCt + 1] == P[i] ) ++LgCt;
Pi[i] = LgCt;
}
}
inline void KMP()
{
Sol[0] = 0;
for( LgCt = 0, i = 1; i <= LgS; ++i )
{
for( ; P[LgCt + 1] != S[i] && LgCt; LgCt = Pi[LgCt] );
if( P[LgCt + 1] == S[i] ) ++LgCt;
if( LgCt == LgP )
{
LgCt = Pi[LgP];
if( Sol[0] < 1000 )
Sol[ ++Sol[0] ] = i - LgP + 1;
else break;
}
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets( P + 1, LMAX, stdin );
LgP = strlen( P + 1 ) - 1;
fgets( S + 1, LMAX, stdin );
LgS = strlen( S + 1 ) - 1;
Prefix();
KMP();
printf("%d\n", Sol[0] );
for( i = 1; i <= Sol[0]; ++i )
printf("%d ", Sol[i] - 1 );
printf("\n");
return 0;
}