Cod sursa(job #2794708)

Utilizator TghicaGhica Tudor Tghica Data 5 noiembrie 2021 12:17:58
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 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] = 1;
  }
  for( i = s1.size(); i < s2.size(); i++ ) {
    has1 = has1 - ( (long long)s2[i - s1.size()] * pow1 ) % MOD1;
    has1 = ( (long long)has1 * BASE + s2[i] ) % MOD1;
    has2 = has2 - ( (long long)s2[i - s1.size()] * pow2 ) % MOD2;
    has2 = ( (long long)has2 * BASE + s2[i] ) % MOD2;
    if( pattern1 == has1 && pattern2 == has2 && verif( i ) && k <= 1000 ) {
      k++;
      rez[k] = i - s1.size() + 1;
    }
  }
  cout<<k<<"\n";
  for( i = 1; i <= k; i++ ) {
    cout<<rez[i]<<" ";
  }
  return 0;
}