Pagini recente » Cod sursa (job #3000848) | Cod sursa (job #62814) | Cod sursa (job #2105098) | Cod sursa (job #271556) | Cod sursa (job #1308544)
#include <fstream>
#include <cstring>
#include <stdio.h>
#include <cstring>
#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 make_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;
}
}
int main()
{
int i, q = 0;
char delim = '\n';
f.get(A, 2000, delim);
f.get();
f.get(B, 2000, delim);
N = strlen(A);
M = strlen(B);
for(i = N + 1 ; i >= 1 ; --i)
A[i] = A[i - 1];
for(i = M + 1 ; i >= 1 ; --i)
B[i] = B[i - 1];
make_pref();
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];
}
}
g<<nr<<'\n';
for(i = 1 ; i <= minim(nr, 1000) ; ++i)
g<<solutii[i]<<' ';
return 0;
}