Pagini recente » Cod sursa (job #727897) | Statistici Alexandru-Andrei Madaras (AlexMadaras00) | Cod sursa (job #2200730) | Cod sursa (job #906869) | Cod sursa (job #1208340)
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define NMax 2000001
int M, N;
char A[NMax], B[NMax];
int pi[NMax], pos[1024];
FILE *in, *out;
void makePrefix(){
int q = 0;
pi[1] = 0;
for(int i = 2; i <= M; i++){
while(q && A[q + 1] != A[i])
q = pi[q];
if (A[q + 1] == A[i])
q++;
pi[i] = q;
}
}
int main(){
in = fopen("strmatch.in", "r");
out = fopen("strmatch.out", "w");
fscanf(in, "%s%s", A + 1, B + 1);
M = strlen(A + 1);
N = strlen(B + 1);
makePrefix();
int q = 0, nr = 0;
for(int i = 1; i <= N; i++){
while (q && A[q + 1] != B[i])
q = pi[q];
if (A[q + 1] == B[i])
++q;
if (q == M){
nr++;
if ( nr <= 1000)
pos[nr] = i - q;
}
}
fprintf(out, "%d\n", nr);
for (int i = 1; i <= std::min(nr, 1000); i++){
fprintf(out, "%d ", pos[i]);
}
fclose(in);
fclose(out);
return 0;
}