Pagini recente » Cod sursa (job #1275385) | Cod sursa (job #3186804) | Cod sursa (job #3227091) | Cod sursa (job #1625997) | Cod sursa (job #1904531)
#include <stdio.h>
#include <ctype.h>
#define buff_size 1<<17
#define nmax 2000000
#define ansmax 1000
char buffer[buff_size];
int poz_buff=buff_size;
FILE *fin, *fout;
int poza, pozb, poz_ans;
char v[2][nmax];
int pi[nmax];
int ans[ansmax];
int co;
char getch() {
if ( poz_buff == buff_size ) {
poz_buff = 0;
fread( buffer, 1, buff_size, fin );
}
return buffer[ poz_buff++ ];
}
void preinitializare_pi() {
int lung, i;
lung = 0;
for ( i = 2; i <= poza; i++ ) {
while ( lung > 0 && v[0][ lung + 1 ] != v[0][i] )
lung = pi[lung];
if ( v[0][ lung + 1 ] == v[0][i] )
lung++;
pi[i] = lung;
}
}
void kmp() {
int lung, i;
lung = 0;
for ( i = 1; i <= pozb; i++ ) {
while ( lung > 0 && v[0][ lung + 1 ] != v[1][i] )
lung = pi[lung];
if ( v[0][ lung + 1 ] == v[1][i] )
lung++;
if ( lung == poza ) {
co++;
if ( poz_ans < ansmax ) {
ans[poz_ans] = i - poza;
poz_ans++;
}
}
}
}
int main() {
int i;
char ch;
fin = fopen( "strmatch.in", "r" );
ch = getch();
while ( isalpha(ch) != 0 ) {
v[0][++poza] = ch;
ch = getch();
}
ch = getch();
while ( isalpha(ch) != 0 ) {
v[1][++pozb] = ch;
ch = getch();
}
fclose( fin );
preinitializare_pi();
kmp();
fout = fopen( "strmatch.out", "w" );
fprintf( fout, "%d\n", co );
for ( i = 0; i < poz_ans; i++ )
fprintf( fout, "%d ", ans[i] );
fputc( '\n', fout );
fclose( fout );
return 0;
}