Cod sursa(job #2979049)

Utilizator raresgherasaRares Gherasa raresgherasa Data 14 februarie 2023 19:00:53
Problema Potrivirea sirurilor Scor 94
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

const int mod1 = 1e9 + 9;
const int mod2 = 666013;

const int kN = 2e6 + 5;

int cnt;
long long h1[kN], h2[kN], hS1, hS2;
char s[kN], t[kN];
bitset<kN>used;

int main(){
   ios_base::sync_with_stdio(false);

   fin >> s >> t;

   int S = (int)strlen(s);
   int T = (int)strlen(t);

   long long p1 = 1, p2 = 1;
   for (int i = 0; i < S; i++){
      hS1 = (hS1 + (s[i] - 'A' + 1) * p1) % mod1;
      hS2 = (hS2 + (s[i] - 'A' + 1) * p2) % mod2;
      p1 = (p1 * 61) % mod1;
      p2 = (p2 * 61) % mod2;
   }

   p1 = p2 = 1;
   for (int i = 0; i < T; i++){
      h1[i + 1] = (h1[i] + (t[i] - 'A' + 1) * p1) % mod1;
      h2[i + 1] = (h2[i] + (t[i] - 'A' + 1) * p2) % mod2;
      p1 = (p1 * 61) % mod1;
      p2 = (p2 * 61) % mod2;
   }

   p1 = p2 = 1;
   for (int i = 0; i + S - 1 < T; i++){
      long long cur_h1 = (h1[i + S] - h1[i] + mod1) % mod1;
      long long cur_h2 = (h2[i + S] - h2[i] + mod2) % mod2;
      if (cur_h1 == (hS1 * p1) % mod1 && cur_h2 == (hS2 * p2) % mod2){
         used[i] = true;
         ++cnt;
      }
      p1 = (p1 * 61) % mod1;
      p2 = (p2 * 61) % mod2;
   }

   fout << cnt << '\n';
   cnt = 0;
   for (int i = 0; i < T; i++){
      if (used[i] && cnt < 1000){
         fout << i << " ";
         ++cnt;
      }
   }
}