Pagini recente » Cod sursa (job #569252) | Cod sursa (job #2471360) | Cod sursa (job #1224057) | Cod sursa (job #3030641) | Cod sursa (job #1144817)
#include<fstream>
#include<vector>
#include<string>
using namespace std;
ifstream fin( "strmatch.in" );
ofstream fout( "strmatch.out" );
const int mod = 666013;
string a, b;
int v[ 1000 ];
inline int code( char c ) {
if ( 'a' <= c && c <= 'z' ) {
return c - 'A' + 26;
} else {
return c - 'A';
}
}
int main()
{
int p, ha, hb, sol, k;
fin>>a>>b;
sol = ha = hb = 0;
p = 1;
k = (int)a.size();
if ( k < (int)b.size() ) {
for( int i = k - 1; i >= 0; -- i ) {
ha += p*code( a[i] );
hb += p*code( b[i] );
if ( i > 0 ) {
p *= 52;
p %= mod;
}
}
if ( ha == hb ) {
v[ 0 ] = 0;
++ sol;
}
}
for( int i = k; i < (int)b.size(); ++ i ) {
hb = ( hb - p * code( b[i-k] ) ) * 52 + code( b[i] );
hb %= mod;
if ( hb < 0 ) {
hb += mod;
}
if ( ha == hb ) {
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;
}