Pagini recente » Cod sursa (job #700032) | Cod sursa (job #272276) | Cod sursa (job #3196852) | Cod sursa (job #253617) | Cod sursa (job #1336257)
#include <cstdio>
#include <cstring>
#define DIM 2000013
using namespace std;
FILE *fin=freopen("strmatch.in","r",stdin);
FILE *fout=freopen("strmatch.out","w",stdout);
char X[DIM], Y[DIM];
int L[DIM], D[DIM], Pos[1003];
int n, m, ap;
void Read()
{
gets(X);
gets(Y);
n = strlen(X);
m = strlen(Y);
for(int i = n ; i > 0 ; --i)
X[i] = X[i - 1];
for(int i = m ; i > 0 ; --i)
Y[i] = Y[i - 1];
}
void Build_first()
{
int k = 0;
for(int i = 2; i <= n ; ++i)
{
while( k > 0 && X[i] != X[k + 1] )
k = L[k];
if( X[i] == X[k + 1] )
++k;
L[i] = k;
}
}
int main()
{
Read();
Build_first();
int k = 0;
for(int i = 1; i <= m ; ++i)
{
while( k > 0 && Y[i] != X[k + 1] )
k = L[k];
if( Y[i] == X[k + 1] )
++k;
D[i] = k;
if( D[i] == n )
{
++ap;
if( ap <= 1000 )
Pos[ap] = i - n;
}
}
printf("%d\n", ap);
for(int i = 1; i <= ap && i <= 1000; ++i)
printf("%d ", Pos[i]);
return 0;
}