Pagini recente » Cod sursa (job #1739929) | Monitorul de evaluare | Cod sursa (job #707098) | Cod sursa (job #827706) | Cod sursa (job #1904553)
#include <fstream>
#include <string.h>
using namespace std;
#include <ctype.h>
#define buff_size 1<<17
#define nmax 2000001
#define ansmax 1000
char buffer[buff_size];
int poz_buff = buff_size;
//FILE *fin, *fout;
ifstream fin( "date.in" );
ofstrean fout( "date.out" );
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++;
}
lung = pi[lung];
}
}
}
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 );
*/
fin >> v[0] >> v[1];
poza = strlen( v[0] );
pozb = strlen( v[1] );
preinitializare_pi();
kmp();
//fout = fopen( "strmatch.out", "w" );
//fprintf( fout, "%d\n", co );
fout << co << '\n';
for ( i = 0; i < poz_ans; i++ )
//fprintf( fout, "%d ", ans[i] );
fout << ans[i] << " ";
//fputc( '\n', fout );
fout << "\n";
//fclose( fout );
fin.close();
fout.close();
return 0;
}