Pagini recente » Cod sursa (job #1165027) | Cod sursa (job #43445) | Cod sursa (job #969219) | Cod sursa (job #2576092) | Cod sursa (job #1146323)
#include<fstream>
#include<vector>
#include<string>
using namespace std;
ifstream fin( "strmatch.in" );
ofstream fout( "strmatch.out" );
const int mod1 = 12974;
const int mod2 = 96235;
const int base = 256;
string a, b;
int v[ 1000 ];
int main()
{
int p1, p2, sol, k;
long long hb1, hb2, ha1, ha2;
fin>>a>>b;
sol = ha1 = ha2 = hb1 = hb2 = 0;
p1 = p2 = 1;
k = (int)a.size();
if ( k < (int)b.size() ) {
for( int i = k - 1; i >= 0; -- i ) {
ha1 += p1 * a[i]; ha2 += p2 * a[i];
hb1 += p1 * b[i]; hb2 += p2 * b[i];
ha1 %= mod1; hb1 %= mod1;
ha2 %= mod2; hb2 %= mod2;
if ( i > 0 ) {
p1 *= base; p2 *= base;
p1 %= mod1; p2 %= mod2;
}
}
if ( ha1 == hb1 && ha2 == hb2 ) {
v[ 0 ] = 0;
++ sol;
}
}
for( int i = k; i < (int)b.size(); ++ i ) {
hb1 = ( hb1 - p1 * b[i-k] ) * base + b[i];
hb2 = ( hb2 - p2 * b[i-k] ) * base + b[i];
hb1 %= mod1; hb2 %= mod2;
if ( hb1 < 0 ) {
hb1 += mod1;
}
if ( hb2 < 0 ) {
hb2 += mod2;
}
if ( ha1 == hb1 && ha2 == hb2 ) {
if ( sol < 1000 )
v[ sol ] = i - k + 1;
++ sol;
}
}
fout<<sol<<'\n';
sol = sol<1000?sol:1000;
for( int i = 0; i < sol; ++ i ) {
fout<<v[i]<<' ';
}
fin.close();
fout.close();
return 0;
}