Pagini recente » Cod sursa (job #3363220) | Cod sursa (job #3361354) | Cod sursa (job #3361423) | Cod sursa (job #3361362) | Cod sursa (job #3363177)
#include <bits/stdc++.h>
using namespace std;
const int MAXB = 2e6 , BZH = 67 , MODH = 1e9 + 7 , MAXI = 1e3 , BZH2 = 71 , MODH2 = 1e9 + 9;
int hb[2][MAXB + 1] , idx[MAXI + 1] , pb[2][MAXB + 1] , ib[2][MAXB + 1] , ha[2];
int conv ( char ch ) {
if ( 'A' <= ch && ch <= 'Z' )
return ch - 'A' + 1;
else if ( 'a' <= ch && ch <= 'z' )
return ch - 'a' + 27;
else
return ch - '0' + 53;
}
int mypow ( int b , int e , int mod ) {
int rez;
rez = 1;
while ( e > 0 ) {
if ( e % 2 == 1 )
rez = ( long long ) rez * b % mod;
b = ( long long ) b * b % mod;
e = e / 2;
}
return rez;
}
int get ( int dr , int st ) {
return ( hb[0][dr] - hb[0][st - 1] + MODH ) % MODH * ( long long ) ib[0][st - 1] % MODH;
}
int get1 ( int dr , int st ) {
return ( hb[1][dr] - hb[1][st - 1] + MODH2 ) % MODH2 * ( long long ) ib[1][st - 1] % MODH2;
}
void calcPb () {
int i;
pb[0][0] = 1;
for ( i = 1 ; i <= MAXB ; i++ )
pb[0][i] = ( long long ) pb[0][i - 1] * BZH % MODH;
ib[0][MAXB] = mypow ( pb[0][MAXB] , MODH - 2 , MODH );
for ( i = MAXB - 1 ; i > 0 ; i-- )
ib[0][i] = ( long long ) ib[0][i + 1] * BZH % MODH;
pb[1][0] = 1;
for ( i = 1 ; i <= MAXB ; i++ )
pb[1][i] = ( long long ) pb[1][i - 1] * BZH2 % MODH2;
ib[1][MAXB] = mypow ( pb[1][MAXB] , MODH2 - 2 , MODH2 );
for ( i = MAXB - 1 ; i > 0 ; i-- )
ib[1][i] = ( long long ) ib[1][i + 1] * BZH2 % MODH2;
}
int main () {
ifstream fin ( "strmatch.in" );
ofstream fout ( "strmatch.out" );
char la , lb;
int lenb , lena , i , leni;
calcPb ();
fin.get ( la );
lena = 0;
while ( la != '\n' ) {
ha[0] = ( ha[0] + ( long long ) conv ( la ) * pb[0][lena] % MODH ) % MODH;
ha[1] = ( ha[1] + ( long long ) conv ( la ) * pb[1][lena] % MODH2 ) % MODH2;
lena++;
fin.get ( la );
}
fin.get ( lb );
lenb = 1;
while ( lb != '\n' ) {
hb[0][lenb] = ( hb[0][lenb - 1] + ( long long ) conv ( lb ) * pb[0][lenb - 1] % MODH ) % MODH;
hb[1][lenb] = ( hb[1][lenb - 1] + ( long long ) conv ( lb ) * pb[1][lenb - 1] % MODH2 ) % MODH2;
lenb++;
fin.get ( lb );
}
lenb--;
leni = 0;
for ( i = lena ; i <= lenb ; i++ )
if ( get ( i , i - lena + 1 ) == ha[0] && get1 ( i , i - lena + 1 ) == ha[1] )
if ( leni < MAXI )
idx[++leni] = i - lena;
fout << leni << '\n';
for ( i = 1 ; i <= leni ; i++ )
fout << idx[i] << ' ';
fout.put ( '\n' );
return 0;
}