Pagini recente » Cod sursa (job #2248800) | Cod sursa (job #842584) | Cod sursa (job #1831007) | Cod sursa (job #533883) | Cod sursa (job #1631968)
/**
* Code by Patrick Sava
* "Spiru Haret" National College of Bucharest
**/
# include "fstream"
# include "cstring"
# include "vector"
# include "queue"
# include "bitset"
# include "algorithm"
# include "map"
# include "set"
# include "unordered_map"
# include "deque"
# include "string"
# include "iomanip"
# include "cmath"
# include "stack"
# include "cassert"
const char IN [ ] = "strmatch.in" ;
const char OUT [ ] = "strmatch.out" ;
using namespace std ;
# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( register int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( register int a = b ; a >= c ; -- a )
ifstream cin ( IN ) ;
ofstream cout ( OUT ) ;
const int MAX = 4e6 + 14 ;
char sir [ MAX ] ;
int z [ MAX ] ;
int cate ;
vector < int > sol ;
int main ( void )
{
cin >> ( sir + 1 ) ;
int l = strlen ( sir + 1 ) ;
sir [ l + 1 ] = '#' ;
cin >> ( sir + l + 2 ) ;
int n = strlen ( sir + 1 ) ;
int L = 1 ;
int R = 1 ;
z [ 1 ] = 0 ;
int bucluc = l + 1 ;
FORN ( i , 2 , n )
{
if ( sir [ i ] == '#' ) continue ;
if ( R < i ) {
while ( i + z [ i ] <= n and sir [ i + z [ i ] ] == sir [ z [ i ] + 1 ] )
++ z [ i ] ;
R = i + z [ i ] - 1 ;
L = i ;
if ( z [ i ] == l and i > l ) {
++ cate ;
if ( cate <= 1000 ) {
sol.pb ( i - ( l + 1 ) - 1 ) ;
}
}
//cout << z [ i ] << ' ' ;
continue ;
}
int oo = i - L + 1 ;
z [ i ] = z [ oo ] ;
if ( i < R ) {
z [ i ] = min ( z [ oo ] , R - i ) ;
}
while ( i + z [ i ] <= n and sir [ i + z [ i ] ] == sir [ z [ i ] + 1 ] )
++ z [ i ] ;
if ( i + z [ i ] - 1 > R ) {
L = i ;
R = i + z [ i ] - 1 ;
}
if ( z [ i ] == l and i > l ) {
++ cate ;
if ( cate <= 1000 ) {
sol.pb ( i - ( l + 1 ) - 1 ) ;
}
}
//cout << z [ i ] << ' ' ;
}
//return 0 ;
//cout << endl ;
cout << cate << '\n' ;
for ( auto x : sol )
cout << x << ' ' ;
return 0;
}