Pagini recente » Cod sursa (job #1076697) | Cod sursa (job #704390) | Cod sursa (job #434290) | Cod sursa (job #964410) | Cod sursa (job #1456016)
/*
Strmatch using Z-Algorithm
Coded by: "Emanuel Nrx"
*/
#include <cstdio>
#include <cstring>
#define DIM 2097152
using namespace std;
int Z[DIM*2], L, R, P[1001], R2, L2, N, M, i, j, nr, val, K;
char S[DIM*2], A[DIM], B[DIM];
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[1] = N + M;
for(int i = 2; i <= N + M; i ++){
if(S[i] != S[1]){
L = 0;
R = 0;
Z[i] = 0;
}
else{
if(S[i] > R){
L = i;
R = i;
while(S[R-L+2] == S[R+1])
R ++;
Z[i] = R - L + 1;
}
else{
if(i + Z[i] < R){
Z[i] = Z[i-L+1];
L = L;
R = R;
}
else{
L = i;
R = R;
while(S[R-L+2] == S[R+1])
R ++;
Z[i] = R - L + 1;
}
}
}
if(Z[i] >= N && i > N && nr < 1000)
P[++nr] = i - N - 1;
}
printf("%d\n", nr);
for(int i = 1; i <= nr; i ++)
printf("%d ", P[i]);
fclose(stdin );
fclose(stdout);
return 0;
}