Pagini recente » Cod sursa (job #3120916) | wrtyer | Cod sursa (job #1823878) | Cod sursa (job #1892765) | Cod sursa (job #1745953)
# include <iostream>
# include <fstream>
# include <stdio.h>
# include <stdlib.h>
# include <algorithm>
# include <vector>
# include <cstring>
using namespace std;
# define MAX_LEN 2000001
int pi[MAX_LEN];
char a[1 + MAX_LEN];
char b[1 + MAX_LEN];
vector<int> rez;
class ifbuffer {
private:
char text[100000];
int size;
int pos;
bool isDigit[128];
bool isBlank[128];
FILE *file;
inline void refill( void ) {
pos = 0;
fread( text, 1, size, file );
}
inline char getc() {
char c = text[pos ++];
if ( pos == size )
refill();
return c;
}
inline int getnr() {
char c = getc();
int nr = 0, p;
while ( !isDigit[c] && c != '-' )
c = getc();
if ( c == '-' ) {
p = -1;
c = getc();
} else
p = 1;
while ( isDigit[c] ) {
nr = nr * 10 + c - '0';
c = getc();
}
return nr * p;
}
public:
inline ifbuffer( char * path, int s = 100000 ) {
size = s;
file = fopen( path, "r" );
int i;
for ( i = 0; i < 128; i ++ )
isDigit[i] = isBlank[i] = false;
for ( i = '0'; i <= '9'; i ++ )
isDigit[i] = true;
isBlank[' '] = isBlank['\n'] = true;
refill();
}
inline ifbuffer &operator>>( int &v ) {
v = getnr();
return *this;
}
inline ifbuffer &operator>>( char &v ) {
v = getc();
return *this;
}
inline ifbuffer &operator>>( char * v ) {
char ch;
do {
ch = getc();
} while ( isBlank[ch] );
while ( !isBlank[ch] ) {
*(v ++) = ch;
ch = getc();
}
return *this;
}
inline void close() {
fclose( file );
}
};
class ofbuffer {
private:
char text[100000];
int size;
int pos;
bool isDigit[128];
FILE *file;
inline void clear( void ) {
pos = 0;
fwrite( text, 1, size, file );
}
inline void putc( char c) {
text[pos ++] = c;
if ( pos == size )
clear();
}
inline void putnr( int nr ) {
if ( nr < 0 ) {
putc( '-' );
nr =- nr;
}
int p10;
for ( p10 = 1; p10 * 10LL <= nr; p10 *= 10 );
for ( ; p10 > 0; p10 /= 10 )
putc( nr / p10 % 10 + '0' );
}
public:
inline ofbuffer( char * path, int s = 100000 ) {
size = s;
file = fopen( path, "w" );
int i;
for ( i = 0; i < '0'; i ++ )
isDigit[i] = false;
for ( i = '0'; i <= '9'; i ++ )
isDigit[i] = true;
for ( i = '9' + 1; i < 128; i ++ )
isDigit[i] = false;
}
inline ofbuffer &operator<<( int v ) {
fprintf( file, "%d", v );
return *this;
}
inline ofbuffer &operator<<( char v ) {
fputc( v, file );
return *this;
}
inline void close() {
fclose( file );
}
};
int main() {
ifbuffer fin( "strmatch.in" );
ofbuffer fout( "strmatch.out" );
int i, k, r, n, m, s;
fin >> a + 1 >> b + 1;
n = strlen( a + 1 );
m = strlen( b + 1 );
pi[0] = -1;
k = r = 0;
for ( i = 1; i <= m; i ++ ) {
while ( k != -1 && b[i] != a[k + 1] )
k = pi[k];
k ++;
pi[i] = k;
if ( k == n )
rez.push_back( i - n );
}
fout << (int) rez.size() << '\n';
s = min( (int)rez.size(), 1000 );
for ( i = 0; i < s; i ++ )
fout << rez[i] << ' ';
fin.close();
fout.close();
return 0;
}