Pagini recente » Cod sursa (job #3187624) | Cod sursa (job #660396) | Cod sursa (job #251941) | Cod sursa (job #2021419) | Cod sursa (job #2257843)
#include <bits/stdc++.h>
#define maxl 2000000
#define pow1 73
#define mod 100007
#define maxaf 1000
using namespace std;
char a[maxl+5], v[maxl+5];
int match[maxaf+5];
int i_mt;
int main ()
{
ifstream fin ( "strmatch.in" );
ofstream fout ( "strmatch.out" );
fin >> a >> v;
int la = strlen ( a ), lv = strlen ( v );
int i, p = 1, hhc = 0, hht = 0;
for ( i = 0; i < la; i++ )
{
if ( i < la - 1 )
p = ( p * pow1 ) % mod;
hhc = ( hhc * pow1 + a[i] ) % mod;
hht = ( hht * pow1 + v[i] ) % mod;
}
for ( i = la; i < lv; i++ )
{
if ( hhc == hht )
{
if ( i_mt < maxaf )
match[i_mt] = i - la;
i_mt++;
}
hht = ( hht - ( v[i-la] * p ) % mod + mod ) * pow1 + v[i];
hht %= mod;
}
if ( hhc == hht )
{
if ( i_mt < maxaf )
match[i_mt] = i - la;
i_mt++;
}
fout << i_mt << '\n';
i_mt = min ( i_mt, maxaf );
for ( i = 0; i < i_mt; i++ )
fout << match[i] << ' ';
fin.close ();
fout.close ();
return 0;
}