Cod sursa(job #2416294)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 27 aprilie 2019 12:24:17
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#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;
}