Pagini recente » Cod sursa (job #112743) | Cod sursa (job #601845) | Statistici Hapaianu Rares (Rares_Hap) | Cod sursa (job #291505) | Cod sursa (job #2227091)
#include <fstream>
#include <cstring>
#define maxn 2000000
#define pow1 73
#define mod1 100007
#define mod2 100019
using namespace std;
char a[maxn];
char v[maxn];
int match[maxn];
int ind = 0;
bool comp ( int st1, int dr1, int st2 )
{
while ( st1 <= dr1 && a[st1] == v[st2] )
{
st1++;
st2++;
}
return st1 > dr1;
}
char conv ( char ch )
{
if ( ch >= 'a' && ch <= 'z' )
return ch - 'a' + 1;
else if ( ch >= 'A' && ch <= 'Z' )
return 27 + ch - 'A';
else
return 53 + ch - '0';
}
int resetm ( int &hh, int mod )
{
if ( hh < 0 )
hh += mod;
}
int main ()
{
ifstream fin ( "strmatch.in" );
ofstream fout ( "strmatch.out" );
fin.getline ( a, maxn );
fin.getline ( v, maxn );
int hashc1 = 0, hashc2 = 0; /// hash corect
int hasht1 = 0, hasht2 = 0; /// hash test
int i, la = strlen ( a ), lv = strlen ( v );
for ( i = 0; i < la; i++ )
a[i] = conv ( a[i] );
for ( i = 0; i < lv; i++ )
v[i] = conv ( v[i] );
if ( la > lv )
{
fout << '0';
return 0;
}
int p1 = 1, p2 = 1;
for ( i = 0; i < la - 1; i++ )
{
p1 = ( p1 * pow1 ) % mod1;
p2 = ( p2 * pow1 ) % mod2;
}
/// hash corect
for ( i = 0; i < la; i++ )
{
hashc1 = ( hashc1 * pow1 + a[i] ) % mod1;
hashc2 = ( hashc2 * pow1 + a[i] ) % mod2;
}
resetm ( hashc1, mod1 ); resetm ( hashc2, mod2 );
/// hash de start
for ( i = 0; i < la; i++ )
{
hasht1 = ( hasht1 * pow1 + v[i] ) % mod1;
hasht2 = ( hasht2 * pow1 + v[i] ) % mod2;
}
resetm ( hasht1, mod1 ); resetm ( hasht2, mod2 );
for ( i = la; i < lv; i++ )
{
if ( hashc1 == hasht1 && hashc2 == hasht2 && comp ( 0, la - 1, i - la ) == true )
match[ind++] = i - la;
hasht1 = ( hasht1 - ( v[i-la] * p1 ) % mod1 + mod1 ) * pow1 + v[i];
hasht1 %= mod1;
resetm ( hasht1, mod1 );
hasht2 = ( hasht2 - ( v[i-la] * p2 ) % mod2 + mod2 ) * pow1 + v[i];
hasht2 %= mod2;
resetm ( hasht2, mod2 );
}
if ( hashc1 == hasht1 && hashc2 == hasht2 )
match[ind++] = i - la;
fout << ind << '\n';
if ( ind > 1000 )
ind = 1000;
for ( i = 0; i < ind; i++ )
fout << match[i] << ' ';
fin.close ();
fout.close ();
return 0;
}