Cod sursa(job #2595494)

Utilizator avtobusAvtobus avtobus Data 7 aprilie 2020 20:15:02
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
// another implementation using Rabin-Karp
#include <stdio.h>
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < n; i++)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int INF = 0x3f3f3f3f;

int P = 97;

const int mod1 = 100103;
const int mod2 = 100109;

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

string A,B;

int main(void) {
  fin >> A >> B;
  int N = A.size(), M = B.size();

  if(M < N) {
    cout << 0 << endl;
    return 0;
  }

  int p1 = 1; // P^N % mod1;
  int p2 = 1; // P^N % mod2;

  int h1 = 0;
  int h2 = 0;
  for(auto a: A) {
    h1 = (h1*P + a) % mod1;
    h2 = (h2*P + a) % mod2;

    p1 = (p1*P) % mod1;
    p2 = (p2*P) % mod2;
  }

  //  The rolling hashes based on B
  int hb1 = 0;
  int hb2 = 0;
  rep(i, N) {
    hb1 = (hb1*P + B[i]) % mod1;
    hb2 = (hb2*P + B[i]) % mod2;
  }

  vi res;
  int result = 0;
  if (hb1 == h1 && hb2 == h2) { res.push_back(0); result++; }

  for(int i = N; i < M; i++) {
    hb1 = ((hb1*P + B[i]) % mod1 - (B[i-N]*p1) % mod1 + mod1) % mod1;
    hb2 = ((hb2*P + B[i]) % mod2 - (B[i-N]*p2) % mod2 + mod2) % mod2;
    if (hb1 == h1 && hb2 == h2) {
      result++;
      if (res.size() < 1000) { res.push_back(i - (N-1)); }
    }
  }

  cout << result << '\n';
  for(auto pos: res) {
    cout << pos << ' ';
  }
  cout << '\n';

  return 0;
}