Pagini recente » Cod sursa (job #2573100) | Cod sursa (job #841086) | Cod sursa (job #2581013) | Cod sursa (job #406015) | Cod sursa (job #2416294)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin( "strmatch.in" );
ofstream fout( "strmatch.out" );
const int MOD1 = 1000000007;
const int MOD2 = 1000000007;
int N, M;
string pat;
string A;
int h, d;
vector <int> sol;
void Read()
{
fin >> pat >> A;
fin.close();
}
inline int Nr( const char & c )
{
if( 'A' <= c && c <= 'Z' ) return c - 'A';
if( 'a' <= c && c <= 'z' ) return 26 + c - 'a';
if( '0' <= c && c <= '9' ) return 26 + 26 + c - '0';
}
inline bool Check( int pos )
{
for( int i = pos; i < pos + pat.size(); ++i )
if( A[i] != pat[i - pos] ) return false;
return true;
}
void Do()
{
if( pat.size() > A.size() )
{
fout << "0\n";
return;
}
d = 26 + 26 + 10;
h = 1;
for( int i = 1; i < pat.size(); ++i )
h = ( h * d ) % MOD1;
int t_hash = 0, p_hash = 0;
for( int i = 0; i < pat.size(); ++i )
p_hash = ( p_hash * d + Nr( pat[i] ) ) % MOD1;
for( int i = 0; i < pat.size(); ++i )
t_hash = ( t_hash * d + Nr( A[i] ) ) % MOD1;
if( p_hash == t_hash && Check( 0 ) ) sol.push_back( 0 );
int aux = pat.size();
for( int i = 1; i + aux - 1 < A.size(); ++i )
{
t_hash = ( 1LL * d * ( t_hash - Nr( A[i - 1] ) * h ) + 1LL * Nr( A[i + aux - 1] ) ) % MOD1;
if( t_hash < 0 ) t_hash += MOD1;
if( t_hash == p_hash && Check( i ) ) sol.push_back( i );
}
fout << sol.size() << '\n';
for( int i = 0; i < min( 1000, (int)sol.size() ); ++i )
fout << sol[i] << ' ';
}
int main()
{
Read();
Do();
return 0;
}