Pagini recente » Borderou de evaluare (job #41814) | Borderou de evaluare (job #3215132) | Cod sursa (job #1308577)
#include <fstream>
#include <cstring>
#include <stdio.h>
#define nmax 2000500
#define minim(a, b) ((a < b) ? a : b)
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int N, M, pr[nmax], nr, solutii[2000];
char A[nmax], B[nmax];
void pref(){
int q = 0, i;
for(i = 2 , pr[1] = 0 ; i <= N ; ++i){
while(q && A[q + 1] != A[i])
q = pr[q];
if(A[q + 1] == A[i])
++q;
pr[i] = q;
}
}
void KMP(){
int i, q = 0;
for(i = 1 ; i <= M ; ++i){
while(q && A[q + 1] != B[i])
q = pr[q];
if(A[q + 1] == B[i])
++q;
if(q == N){
++nr;
if(nr <= 1000)
solutii[nr] = i - q;
q = pr[N];
}
}
}
int main()
{
int i;
FILE *fin, *fout;
fin = fopen("strmatch.in", "r");
fout = fopen("strmatch.out", "w");
fgets(A, sizeof(A), fin);
fgets(B, sizeof(B), fin);
N = strlen(A) - 1;
M = strlen(B) - 1;
for(i = N ; i >= 1 ; --i)
A[i] = A[i - 1];
for(i = M ; i >= 1 ; --i)
B[i] = B[i - 1];
pref();
KMP();
fprintf(fout, "%d\n", nr);
for (i = 1; i <= minim(nr, 1000); ++i) {
fprintf(fout, "%d ",solutii[i]);
}
fprintf(fout, "\n");
return 0;
}