Cod sursa(job #2946931)

Utilizator RolandPetreanPetrean Roland RolandPetrean Data 25 noiembrie 2022 13:48:05
Problema Potrivirea sirurilor Scor 26
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
// https://www.infoarena.ro/problema/strmatch
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

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

const long long x=31, m=1e9;

int main() {
  string a, b;
  fin>>a>>b;
  int n=a.size(), m=b.size();
  
  vector<int> p(max(n,m)+1);
  p[0] = 1;
  for (int i=1; i<p.size(); ++i) p[i] = (p[i-1]*x)%m;

  int a_h=0;
  vector<int> b_h(m);
  for (int i=1; i<m; ++i) b_h[i] = (b_h[i-1] + ((int)b[i]) * p[i])%m;
  for (int i=0; i<n; ++i) a_h = (a_h + ((int)a[i]) * p[i])%m;

  vector<int> found;
  for (int i=0; i+n-1<m; ++i) {
    int curr = (b_h[i+n-1] - (i ? b_h[i-1] : 0) + m)%m;
    if (curr==a_h*p[i]%m) found.push_back(i);
  }
  fout<<found.size()<<endl;
  for (int v:found) fout<<v<<" ";
}