Cod sursa(job #1800388)

Utilizator tudorcomanTudor Coman tudorcoman Data 7 noiembrie 2016 18:57:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb

#include <cstdio>
#include <cstring>
#include <functional>
#include <vector>
using namespace std;

const int lmax = 2000005;
const int mod1 = 100007;
const int mod2 = 100021;

char A[lmax], B[lmax];

int main() {
  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);

  gets(A);
  gets(B);

  int n = strlen(A), N = strlen(B);

  pair<int, int> kA = make_pair(0, 0), put = make_pair(1, 1), ksecv = make_pair(0, 0);

  for(int i = n - 1; i >= 0; -- i) {
    kA.first =     (kA.first     + (put.first  * A[i])) % mod1;
    kA.second =    (kA.second    + (put.second * A[i])) % mod2;
    ksecv.first =  (ksecv.first  + (put.first  * B[i])) % mod1;
    ksecv.second = (ksecv.second + (put.second * B[i])) % mod2;
    if(i > 0) {
      put.first = put.first * 73 % mod1;
      put.second = put.second * 73 % mod2;
    }
  }

  vector<int> positions;
  if(kA.first == ksecv.first and kA.second == ksecv.second)
    positions.push_back(0);

  for(int i = n; i < N; ++ i) {
    ksecv.first =  ((ksecv.first  -   (B[i - n] * put.first)  % mod1 + mod1) * 73 + B[i]) % mod1;
    ksecv.second = ((ksecv.second -   (B[i - n] * put.second) % mod2 + mod2) * 73 + B[i]) % mod2;
    if(ksecv.first == kA.first and ksecv.second == kA.second)
      positions.push_back(i - n + 1);
  }

  printf("%u\n", positions.size());
  for(int i = 0; i < min((int)positions.size(), 1000); ++ i)
    printf("%d ", positions[i]);
  printf("\n");
  return 0;
}