Cod sursa(job #1800380)

Utilizator tudorcomanTudor Coman tudorcoman Data 7 noiembrie 2016 18:47:25
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb

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

const int lmax = 2000005;
const int miliard = 1000000000;
const int mod1 = miliard + 3;
const int mod2 = miliard + 7;

char A[lmax], B[lmax];

inline int getn(char c) {
  return c - 'A';
}

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     + (1LL * put.first  * getn(A[i]) % mod1)) % mod1;
    kA.second =    (kA.second    + (1LL * put.second * getn(A[i]) % mod2)) % mod2;
    ksecv.first =  (ksecv.first  + (1LL * put.first  * getn(B[i]) % mod1)) % mod1;
    ksecv.second = (ksecv.second + (1LL * put.second * getn(B[i]) % mod2)) % mod2;
    if(i > 0) {
      put.first = put.first * 26LL % mod1;
      put.second = put.second * 26LL % 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 = (26LL * (ksecv.first - (1LL * getn(B[i - n]) * put.first) % mod1) % mod1 + getn(B[i]) % mod1) % mod1;
    ksecv.second = (26LL * (ksecv.second - (1LL * getn(B[i - n]) * put.second) % mod2) % mod2 + getn(B[i]) % mod2) % mod2;
    fprintf(stderr, "%d %d\n", ksecv.first, ksecv.second);
    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;
}