Cod sursa(job #2420496)

Utilizator pickleVictor Andrei pickle Data 12 mai 2019 13:17:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <stdio.h>
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < n; i++)
#define repa(i, l, r) for (int i = l; i < r; i++)
#define repd(i, r, l) for (int i = r; i > l; i--)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int P = 73;
const int mod1 = 100007;
const int mod2 = 100021;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

string A, B;
int main(void) {
  fin >> A >> B;
  int N = A.length();
  int M = B.length();
  if (M < N) {
    fout << 0 << endl;
    return 0;
  }
  int count = 0;
  int P1 = 1; // P^(N-1) % mod1
  int P2 = 1; // P^(N-1) % mod2
  int ah1 = 0; // hash1 of A
  int ah2 = 0; // hash2 of A
  int bh1 = 0; // Rolling hash1 of B
  int bh2 = 0; // Rolling hash2 of B
  for(int i = 0; i < N; ++i) {
    ah1 = (ah1 * P + A[i]) % mod1;
    ah2 = (ah2 * P + A[i]) % mod2;
    bh1 = (bh1 * P + B[i]) % mod1;
    bh2 = (bh2 * P + B[i]) % mod2;

    if (i) {
      P1 = (P1 * P) % mod1;
      P2 = (P2 * P) % mod2;
    }
  }

  vi res;
  if (bh1 == ah1 && bh2 == ah2) {
    res.push_back(0);
    count++;
  }

  for(int i = N; i < M; i++) {
    bh1 = ((bh1 - (B[i-N]*P1) % mod1 + mod1) * P + B[i]) % mod1;
    bh2 = ((bh2 - (B[i-N]*P2) % mod2 + mod2) * P + B[i]) % mod2;

    if (bh1 == ah1 && bh2 == ah2) {
      if (count < 1000)
        res.push_back(i-N+1);
      count++;
    }
  }
  fout << count << endl;
  for(int pos: res)
    fout << pos << ' ';
  fout << endl;
  return 0;
}