Pagini recente » Borderou de evaluare (job #1821766) | Borderou de evaluare (job #1356398) | Cod sursa (job #492007) | Borderou de evaluare (job #2846961) | Cod sursa (job #2176227)
#include <fstream>
#include <cstring>
#define maxn 2000000
#define pow1 73
#define mod 100007
using namespace std;
char a[maxn];
char v[maxn];
int match[maxn];
int ind = 0;
int main ()
{
ifstream fin ( "strmatch.in" );
ofstream fout ( "strmatch.out" );
fin >> a >> v;
int hashc = 0; /// hash corect
int hasht = 0; /// hash test
int i, la = strlen ( a ), lv = strlen ( v );
if ( la > lv )
{
fout << '0';
return 0;
}
int p1 = 1;
for ( i = 0; i < la - 1; i++ )
p1 = ( p1 * pow1 ) % mod;
/// hash corect
for ( i = 0; i < la; i++ )
hashc = ( hashc * pow1 + a[i] ) % mod;
/// hash de start
for ( i = 0; i < la; i++ )
hasht = ( hasht * pow1 + v[i] ) % mod;
for ( i = la; i < lv; i++ )
{
if ( hashc == hasht )
match[ind++] = i - la;
hasht = ( hasht - ( v[i-la] * p1 ) % mod + mod ) * pow1 + v[i];
hasht %= mod;
}
if ( hashc == hasht )
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;
}