Pagini recente » Cod sursa (job #1278315) | Cod sursa (job #1852585) | Cod sursa (job #2962419) | Cod sursa (job #1206651) | Cod sursa (job #1406948)
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
using namespace std;
#define N_MAX 2000001
char A[N_MAX], B[N_MAX];
typedef struct t_matches {
int len, pos[N_MAX];
} t_matches;
t_matches m;
void KMP(char *a , char *S , t_matches *matches ){
matches->len = 0;
int LS = strlen( S );
int La = strlen( a );
char Str[ LS + La + 2 ];
int P[ LS + La + 2 ]; memset(P, 0, sizeof(P));
int fail = 0;
strcpy( Str + 1 , a );
Str[ La + 1 ] = '*';
strcpy( Str + La + 2 , S );
P[1] = 0;
for( int i = 2 ; i <= LS + La + 1 ; i++ ){
fail = P[i-1];
while( Str[fail+1] != Str[i] && fail != 0 )
fail = P[fail];
if( Str[fail+1] == Str[i] )
P[i] = fail + 1;
if( P[i] == La ){
matches->pos[ matches->len++ ] = i - 2 * La - 1;
}
}
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> A >> B;
KMP(A, B, &m);
fout << m.len << "\n";
for (int i = 0; i < m.len; ++i) {
fout << m.pos[i] << " ";
}
fout << "\n";
return 0;
}