Cod sursa(job #2978788)

Utilizator raresgherasaRares Gherasa raresgherasa Data 14 februarie 2023 13:35:40
Problema Potrivirea sirurilor Scor 96
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>

using namespace std;

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

const int kN = 2e6 + 5;
const int mod = 1e9 + 9;

long long h[kN];
char s[kN], t[kN];

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

   fin >> s >> t;
   int S = (int)strlen(s);
   int T = (int)strlen(t);
   if (S > T){
      fout << "0";
      return 0;
   }

   long long p = 1;

   for (int i = 0; i < T; i++){
      h[i + 1] = (h[i] + (t[i] - 'A' + 1) * p) % mod;
      p = (p * 31) % mod;
   }

   p = 1;
   long long hash_s = 0;
   for (int i = 0; i < S; i++){
      hash_s = (hash_s + (s[i] - 'A' + 1) * p) % mod;
      p = (p * 31) % mod;
   }

   vector<int>ans;
   p = 1;
   for (int i = 0; i + S - 1 < T; i++){
      long long cur_h = (h[i + S] - h[i] + mod) % mod;
      if (cur_h == (hash_s * p) % mod){
         ans.push_back(i);
      }
      p = (p * 31) % mod;
   }

   fout << (int)ans.size() << '\n';
   for (int i = 0; i < min(1000, (int)ans.size()); i++){
      fout << ans[i] << ' ';
   }
}