Pagini recente » Cod sursa (job #1356688) | Cod sursa (job #265537) | Cod sursa (job #1023285) | Cod sursa (job #1887139) | Cod sursa (job #1694624)
/**
* Code by Patrick Sava
* "Spiru Haret" National College of Bucharest
**/
# include <bits/stdc++.h>
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 fin ( IN ) ;
ofstream fout ( OUT ) ;
const int MAX = 2e6 + 14 ;
const unsigned int baza = 71 ;
char A [ MAX ] ;
char B [ MAX ] ;
unsigned int h [ MAX ] ;
unsigned int p [ MAX ] ;
unsigned int hash_pe_interval ( int i , int j )
{
return h [ i ] - h [ j + 1 ] * p [ j - i + 1 ] ;
}
vector < int > pozitii ;
int main()
{
fin >> ( A + 1 ) ;
fin >> ( B + 1 ) ;
int lenA = strlen ( A + 1 ) ;
int lenB = strlen ( B + 1 ) ;
p [ 0 ] = 1 ;
FORN ( i , 1 , lenB ) {
p [ i ] = p [ i - 1 ] * baza ;
}
FORNBACK ( i , lenB , 1 ) {
h [ i ] = h [ i + 1 ] * baza + B [ i ] ;
}
unsigned hashA = 0 ;
FORNBACK ( i , lenA , 1 ) {
hashA = hashA * baza + A [ i ] ;
}
int limita = lenB - lenA + 1 ;
int aparitii = 0 ;
FORN ( i , 1 , limita ) {
if ( hash_pe_interval( i , i + lenA - 1 ) == hashA ) {
++ aparitii ;
if ( aparitii <= 1000 ) {
pozitii.pb ( i - 1 ) ;
}
}
}
fout << aparitii << '\n' ;
for ( auto x : pozitii ) {
fout << x << ' ' ;
}
return 0;
}