Pagini recente » Cod sursa (job #435601) | Cod sursa (job #2151297) | Cod sursa (job #361124) | Cod sursa (job #2378277) | Cod sursa (job #1456115)
#include <cstdio>
#include <cstring>
using namespace std;
const int DIM = (1<<21);
int N, M, i, j, k, k2, R, L;
int Z[DIM*2], Sol[2048], nr;
char A[DIM], B[DIM], S[DIM*2];
int main(){
freopen("strmatch.in" ,"r", stdin );
freopen("strmatch.out","w", stdout);
scanf("%s", A + 1); N = strlen(A + 1);
scanf("%s", B + 1); M = strlen(B + 1);
for(int i = 1; i <= N; i ++)
S[i+0] = A[i];
for(int i = 1; i <= M; i ++)
S[i+N] = B[i];
Z[0] = N;
for(int i = 2; i <= N + M; i ++){
if(i > R){
int j = 1;
while(S[j] == S[i+j-1] && j <= N)
j ++;
Z[i] = j - 1;
L = i;
R = L + Z[i] - 1;
}
else {
int K = i - L + 1;
if(Z[K] < R - i + 1){
Z[i] = Z[K];
}
else {
int j = Z[K] + 1;
while(S[j] == S[i+j-1] && j <= N)
j ++;
Z[i] = j - 1;
L = i;
R = L + Z[i] - 1;
}
}
if(Z[i] >= N && i > N){
nr ++;
if(nr <= 1000)
Sol[nr] = i - Z[i] - 1;
}
}
printf("%d\n", nr);
for(int i = 1; i <= nr && i <= 1000; i ++)
printf("%d ", Sol[i]);
fclose(stdin );
fclose(stdout);
return 0;
}