Pagini recente » Cod sursa (job #2930843) | Cod sursa (job #125328) | Cod sursa (job #1307176) | Cod sursa (job #103821) | Cod sursa (job #2227092)
#include <fstream>
#include <cstring>
#define maxn 2000000
#define pow1 73
#define mod1 100007
#define mod2 100019
using namespace std;
char a[maxn+5];
char v[maxn+5];
int match[maxn+5];
int ind = 0;
int main ()
{
ifstream fin ( "strmatch.in" );
ofstream fout ( "strmatch.out" );
fin >> a >> v;
int hashc1 = 0, hashc2 = 0; /// hash corect
int hasht1 = 0, hasht2 = 0; /// hash test
int i, la = strlen ( a ), lv = strlen ( v );
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;
}
/// hash de start
for ( i = 0; i < la; i++ )
{
hasht1 = ( hasht1 * pow1 + v[i] ) % mod1;
hasht2 = ( hasht2 * pow1 + v[i] ) % mod2;
}
for ( i = la; i < lv; i++ )
{
if ( hashc1 == hasht1 && hashc2 == hasht2 )
match[ind++] = i - la;
hasht1 = ( hasht1 - ( v[i-la] * p1 ) % mod1 + mod1 ) * pow1 + v[i];
hasht1 %= mod1;
hasht2 = ( hasht2 - ( v[i-la] * p2 ) % mod2 + mod2 ) * pow1 + v[i];
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;
}