Pagini recente » Cod sursa (job #1518096) | Cod sursa (job #2016389) | knird | Cod sursa (job #2794540) | Cod sursa (job #157776)
Cod sursa(job #157776)
#include <stdio.h>
#define in "strmatch.in"
#define out "strmatch.out"
#define dim 2000013
inline int Minim(int a, int b) {
if ( a < b ) return a;
return b;
}
int N, M, nrSol=0;
int Pi[dim], Sol[1001];
char A1[dim], A2[dim];
int main()
{
freopen(in,"r",stdin);
freopen(out,"w",stdout);
N = M = 0;
fgets( A1, dim-1, stdin );
fgets( A2, dim-1, stdin );
while ( (A1[N] >= 'a' && A1[N] <= 'z') || (A1[N] >= 'A' && A1[N] <= 'Z') || (A1[N] >= '0' && A1[N] <= '9') ) N++;
while ( (A2[M] >= 'a' && A2[M] <= 'z') || (A2[M] >= 'A' && A2[M] <= 'Z') || (A2[M] >= '0' && A2[M] <= '9') ) M++;
for ( int i = N; i; i-- ) A1[i] = A1[i-1];
for ( int i = M; i; i-- ) A2[i] = A2[i-1];
int K;
Pi[1] = K = 0;
for ( int i = 2; i <= N; i++ )
{
while ( K && A1[K+1] != A1[i] ) K = Pi[K];
if ( A1[K+1] == A1[i] ) K++;
Pi[i] = K;
}
K = 0;
for ( int i = 1; i <= M; i++ )
{
while ( K && A1[K+1] != A2[i] ) K = Pi[K];
if ( A1[K+1] == A2[i] ) K++;
if ( K == N )
{
nrSol++;
nrSol<1001?Sol[nrSol]=i-N:1;
}
}
printf("%d\n", nrSol);
for ( int i = 1; i <= Minim(nrSol,1000); i++ )
printf("%d ", Sol[i]);
}