Cod sursa(job #2295646)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 3 decembrie 2018 20:28:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.01 kb
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define mp make_pair
#define CHECK(x) if(!(x)) return false;
#define CHECKRET(x, y) if(!(x)) return (y);
#define SKIP(x) if((x)) continue;
typedef pair<int, int> pii;

#ifdef INFOARENA
#define ProblemName "strmatch"
#else
#define ProblemName "fis"
#endif

#define InFile ProblemName ".in"
#define OuFile ProblemName ".out"

namespace Hashing {
  const int primes[] = { 123456791, 123456803, 123456811, 123456821, 123456841, 123456871, 123456887, 123456919, 123456937, 123456967, 123456979, 123457067, 123457099, 123457121, 123457127, 123457129, 123457157, 123457163, 123457189, 123457199, 123457211, 123457219, 123457237, 123457259, 123457267, 123457277, 123457289, 123457291, 123457309, 123457357, 123457361, 123457423, 123457463, 123457501, 123457517, 123457547, 123457571, 123457619, 123457639, 123457643, 123457657, 123457679, 123457739, 123457753, 123457759, 123457771, 123457783, 123457787, 123457799, 123457837 };

  typedef unsigned int phash;
  typedef phash hsh;

  hsh MOD;
  //bases together with their powers
  vector< pair< hsh, vector< hsh > > > B;

  //operations on hashes
  inline hsh hSub(hsh h1, hsh h2) {
    return (MOD + h1 - h2) % MOD;
  }
  inline hsh hAdd(hsh h1, hsh h2) {
    return (h1 + h2) % MOD;
  }
  inline hsh hMul(hsh h1, hsh h2) {
    return (int)((1LL * h1 * h2) % MOD);
  }

  //initializes the system with random prime numbers
  void init() {
    srand((int)time(NULL));
    int szp = sizeof(primes) / sizeof(primes[0]);
    MOD = primes[rand() % szp];
  }

  //adds a base to the system (usually only one will be needed)
  void addBase(hsh b) {
    B.push_back(mp(b, vector<hsh>()));
  }

  //computes base powers up to the second parameter
  void reBase(int whichBase, int upTo) {
    int from = B[whichBase].second.size();
    if (from >= upTo) return;
    B[whichBase].second.resize(upTo);
    if (from == 0) {
      B[whichBase].second[0] = 1;
      ++from;
    }
    for (; from < upTo; ++from) {
      B[whichBase].second[from] = hMul(B[whichBase].second[from - 1], B[whichBase].first);
    }
  }

  struct instance {
    int whichBase;
    vector<hsh> hashes;

    instance(int baseIndex, int size) {
      whichBase = baseIndex;
      hashes.resize(size);
      reBase(whichBase, size);
    }

    //populates hashes with the values in this range
    template <class ForwardIterator> void compute(ForwardIterator left, ForwardIterator right) {
      hsh H = 0;
      for (int i = 0; left != right; ++i, ++left) {
        H = hAdd(hMul(H, B[whichBase].first), *left);
        hashes[i] = H;
      }
    }

    //returns hash in interval [l, r)
    inline hsh hft(int l, int r) {
      if (l >= r) return 0;
      if (l == 0) return hashes[r - 1];
      return hSub(hashes[r - 1], hMul(hashes[l - 1], B[whichBase].second[r - l]));
    }
  };
};

const int MAXN = 2000011;
const int MAXM = 1000;
int m[MAXM], mnr;
int N, M;
char *s, *p;
const int B = 29;

char phys[2 * MAXN];


char ok[255];

void prec_() {
  memset(ok, 0, sizeof ok);
  for (char a = 'a'; a <= 'z'; ++a)
    ok[a] = ok[a ^ 0x20] = 1;
  for (char a = '0'; a <= '9'; ++a)
    ok[a] = 1;
}

void input() {
  int L = fread(phys, 1, sizeof phys, stdin);
  phys[L] = 0;
  p = phys;
  char *cur = phys;
  for (; ok[*cur]; ++cur);
  M = cur - phys;
  for (; !ok[*cur]; ++cur);
  s = cur;
  N = L - (cur - phys);
  if (N > 0 && s[N - 1] == '\n')
    --N;
}

int main() {
  assert(freopen(InFile, "r", stdin));
  assert(freopen(OuFile, "w", stdout));

  prec_();
  input();

  Hashing::init();
  Hashing::addBase(29);

  Hashing::instance H(0, MAXN);
  H.compute(p, p + M);
  Hashing::hsh HM = H.hft(0, M);

  if (N < M) {
    puts("0");
    return 0;
  }

  H.compute(s, s + N);

  for (int i = M; i <= N; ++i) {
    if (H.hft(i - M, i) == HM) {
      if (mnr < MAXM)
        m[mnr] = i - M;
      ++mnr;
    }
  }
  printf("%d\n", mnr);
  for (int i = 0, lim = (mnr < MAXM) ? mnr : MAXM; i < lim; ++i)
    printf("%d ", m[i]);
  puts("");
  return 0;
}