Cod sursa(job #2339832)

Utilizator alex.cojocaruAlex Cojocaru alex.cojocaru Data 9 februarie 2019 13:43:34
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <string>
#include <stdio.h>
#include <queue>

#define BAZA 27
#define MOD 666013

using namespace std;

string pattern ;
string s ;
queue <int> st ;

int main() {

  ifstream fin ("strmatch.in" ) ;
  ofstream fout ("strmatch.out") ;
  int n, i, counter, P, Pattern, nr, CP ;
  fin >> pattern ;
  fin >> s ;
  P = 1 ;
  Pattern = 0 ;
  for (i = 0 ; i < pattern.size() ; i++ ) {
    Pattern = ( ( ( Pattern % MOD ) * (BAZA % MOD) ) % MOD + (pattern[i] - 'A' + 1 ) ) % MOD ;
    if (i != 0 )
      P = (P * BAZA) % MOD  ;
  }
 // fout << P << "\n" ;
  if (pattern.size() > s.size() ) {
    fout << "0" ;
  }
  else {
    nr = 0 ;
    for (i = 0 ; i < pattern.size() ; i++ )
      nr = ( (nr % MOD ) * (BAZA % MOD) + ( s[i] - 'A' + 1 ) % MOD ) % MOD ;
    //fout << "nr = " << nr << "\n" ;
    if (nr == Pattern )
        st.push(0) ;
    for (i = pattern.size() ; i < s.size() ; i++ ) {
      nr = ( nr  - ( ( (s[i-pattern.size()]- 'A' + 1 ) % MOD ) * ( P % MOD ) ) + MOD ) % MOD ;
      nr = ( (nr * (BAZA % MOD ) ) % MOD + ( s[i] - 'A' + 1 ) % MOD  ) % MOD ;
      //fout << "i = " << i+1 << " nr = " << nr << "\n" ;
       if (nr == Pattern )
        st.push(i - pattern.size()) ;
    }
    fout << st.size() << "\n" ;
    while (!st.empty()) {
      fout << st.front()+1 << " " ;
      st.pop() ;
    }
  }
  return 0 ;
}