Pagini recente » Cod sursa (job #73890) | Cod sursa (job #2331260) | Cod sursa (job #2589966) | Cod sursa (job #923740) | Cod sursa (job #2202964)
#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 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 );
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;
}
/// 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 && comp ( 0, la - 1, i - la ) == true )
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;
}