Cod sursa(job #2736324)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 3 aprilie 2021 12:54:04
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>

using namespace std;

#define int long long

#define debug(x) cerr << #x << " = " << x << "\n";

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

const int pw = 37;
const int mod1 = (int)1e9 + 9;
const int mod2 = (int)1e9 + 7;
const int max_n = (int)2e6 + 5;

char s[max_n], p[max_n];

vector<int> ans;

int32_t main() {
  in >> (p + 1) >> (s + 1);
  int p1 = 1, p2 = 1;
  int a1 = 0, a2 = 0, b1 = 0, b2 = 0;
  int n = (int)strlen(p + 1);
  int m = (int)strlen(s + 1);
  for (int i = 1; i <= n; i++) {
    a1 = (1LL * a1 * pw + p[i]) % mod1;
    a2 = (1LL * a2 * pw + p[i]) % mod2;
    b1 = (1LL * b1 * pw + s[i]) % mod1;
    b2 = (1LL * b2 * pw + s[i]) % mod2;
    if (i > 1) {
      p1 = (1LL * p1 * pw) % mod1;
      p2 = (1LL * p2 * pw) % mod2;
    }
  }
  if (a1 == b1 && a2 == b2) {
    ans.push_back(0);
  }
  for (int i = n + 1; i <= m; i++) {
    b1 = ((1LL * b1 - p1 * s[i - n] + mod1) % mod1 * pw + s[i]) % mod1;
    b2 = ((1LL * b2 - p2 * s[i - n] + mod2) % mod2 * pw + s[i]) % mod2;
    if (a1 == b1 && a2 == b2) {
      ans.push_back(i - n);
    }
  }
  out << (int)ans.size() << "\n";
  for (int i = 0; i < min((int)1000, (int)ans.size()); i++) {
    out << ans[i] << " ";
  }
  return 0;
}