Cod sursa(job #2796117)

Utilizator TghicaGhica Tudor Tghica Data 7 noiembrie 2021 16:49:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <fstream>
#include <string>

#define MOD1 666013
#define MOD2 174763
#define BASE 67

using namespace std;

int pow1, pow2, rez[1001];
string s1, s2;

bool verif( int poz ) {
  int k = s1.size() - 1;
  while( s1[k] == s2[poz] && k >= 0 ) {
    poz--;
    k--;
  }
  if( k == -1 )
    return 1;
  else
    return 0;
}

int main() {
  ifstream cin("strmatch.in");
  ofstream cout("strmatch.out");
  cin>>s1>>s2;
  int i, pattern1 = 0, has1= 0, pattern2 = 0, has2 = 0, k;
  pow1 = 1;
  pow2 = 1;
  pattern1 =  s1[0];
  has1 = s2[0];
  pattern2 =  s1[0];
  has2 = s2[0];
  for( i = 1; i < s1.size(); i++ ) {
    pow1 *= BASE;
    pow1 %= MOD1;
    pattern1 = ( pattern1 * BASE + s1[i] ) % MOD1;
    has1 = ( has1 * BASE + s2[i] ) % MOD1;
    pow2 *= BASE;
    pow2 %= MOD2;
    pattern2 = ( pattern2 * BASE + s1[i] ) % MOD2;
    has2 = ( has2 * BASE + s2[i] ) % MOD2;
  }
  k = 0;
  if( pattern1 == has1 && pattern2 == has2 && verif( s1.size() - 1 ) ) {
    k++;
    rez[k] = 0;
  }

  for( i = s1.size(); i < s2.size(); i++ ) {
    has1 = has1 - ( (long long)s2[i - s1.size()] * pow1 ) % MOD1;
    if( has1 < 0 )
      has1 += MOD1;
    has1 = ( (long long)has1 * BASE + s2[i] ) % MOD1;
    has2 = has2 - ( (long long)s2[i - s1.size()] * pow2 ) % MOD2;
    if( has2 < 0 )
     has2 += MOD2;
    has2 = ( (long long)has2 * BASE + s2[i] ) % MOD2;
    if( pattern1 == has1 && pattern2 == has2 ) {
      k++;
      if( k <= 1000 )
        rez[k] = i - s1.size() + 1;
    }
  }
  cout<<k<<"\n";
  if( k > 1000 )
    k = 1000;
  for( i = 1; i <= k; i++ ) {
    cout<<rez[i]<<" ";
  }
  return 0;
}