Cod sursa(job #1626951)

Utilizator pickleVictor Andrei pickle Data 3 martie 2016 13:05:49
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

const int P = 73;
const int M1 = 100007, M2 = 100021, Nmax = 2000666;

string A, B;
int hash1 = 0, hash2 = 0, h1 = 0, h2 = 0, N = 0, ans[Nmax];
int p1 = 1, p2 = 1;

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

  fin >> A >> B;
  int na = A.size();

  for (size_t i = 0; i < A.size(); ++i) {
    if (i != 0) {
      p1 = (p1 * P) % M1;
      p2 = (p2 * P) % M2;
    }

    hash1 = (hash1 * P + A[i]) % M1;
    hash2 = (hash2 * P + A[i]) % M2;
  }

  for (size_t i = 0; i < A.size(); ++i) {
    h1 = (h1 * P + B[i]) % M1;
    h2 = (h2 * P + B[i]) % M2;
  }

  if (h1 == hash1 && h2 == hash2) {
    ans[N] = 0;
    ++N;
  }

  for (size_t i = A.size(); i < B.size(); ++i) {
    h1 = ((h1 - (p1 * B[i - na]) % M1 + M1) * P + B[i]) % M1;
    h2 = ((h2 - (p2 * B[i - na]) % M2 + M2) * P + B[i]) % M2;
    if(h1 == hash1 && h2 == hash2) {
      if (N < 1000) {
        ans[N] = i - na + 1;
      }
      ++N;
    }
  }
  cout << N << endl;
  for (int i = 0; i < N && i < 1000; ++i) {
    cout << ans[i] << ' ';
  }
  cout << endl;

  return 0;
}