Pagini recente » Cod sursa (job #1360806) | Cod sursa (job #714379) | Cod sursa (job #1922392) | Cod sursa (job #670776) | Cod sursa (job #1251598)
# include <cstring>
# include <cstdio>
# include <algorithm>
#define min(a, b) ((a < b) ? a : b)
#define MAXN 2000003
char X[MAXN], Y[MAXN];
int Pi[MAXN], d[MAXN];
int i, K, N, M;
int nr,n,pos[MAXN];
void constructie_pi()
{
N = strlen(X)-1;
K = 0;
Pi[1] = 0;
for (i = 2; i <= N; ++i)
{
while (K > 0 && X[i] != X[K+1])
K = Pi[K];
if (X[i] == X[K+1]) K = K + 1;
Pi[i] = K;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(X+1, MAXN, stdin);
fgets(Y+1, MAXN, stdin);
X[0] = ' ';
Y[0] = ' ';
X[strlen(X)-1] = Y[strlen(Y)-1] = 0;
M = strlen(Y)-1;
constructie_pi();
K = 0;
for (i = 1; i <= M; ++i)
{
while (K > 0 && Y[i] != X[K+1])
K = Pi[K];
if (Y[i] == X[K+1]) K = K + 1;
d[i] = K;
if(d[i] == N)
{
n++;
if(n <= 1000) pos[n]=i-N;
}
}
printf("%d\n", n);
for (i = 1; i <= min(n, 1000); ++i)
printf("%d ", pos[i]);
return 0;
}