Cod sursa(job #2295609)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 3 decembrie 2018 19:57:56
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.97 kb
#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 long long phash;
  typedef pair<phash, 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 mp((MOD.first + h1.first - h2.first) % MOD.first,
      (MOD.second + h1.second - h2.second) % MOD.second);
  }
  inline hsh hAdd(hsh h1, hsh h2) {
    return mp((h1.first + h2.first) % MOD.first,
      (h1.second + h2.second) % MOD.second);
  }
  inline hsh hMul(hsh h1, hsh h2) {
    return mp((h1.first * h2.first) % MOD.first,
      (h1.second * h2.second) % MOD.second);
  }

  //initializes the system with random prime numbers
  void init() {
    srand((int)time(NULL));
    MOD = mp(0, 0);
    int szp = sizeof(primes) / sizeof(primes[0]);
    while (MOD.first == MOD.second) {
      MOD.first = primes[rand() % szp];
      MOD.second = 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] = mp(1, 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 = mp(0, 0);
      for (int i = 0; left != right; ++i, ++left) {
        H = hAdd(hMul(H, B[whichBase].first), mp(*left, *left));
        hashes[i] = H;
      }
    }

    //returns hash in interval [l, r)
    hsh hft(int l, int r) {
      if (l >= r) return mp(0, 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 = 2000001;
const int MAXM = 1010;
int m[MAXM], mnr;
char buf[MAXN];
int N, M;
const int B = 29;

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

  Hashing::init();
  Hashing::addBase(mp(29, 31));

  scanf("%s", buf);
  M = strlen(buf);
  
  Hashing::instance H(0, MAXN);
  H.compute(buf, buf + M);
  Hashing::hsh HM = H.hft(0, M);

  scanf("%s", buf);
  N = strlen(buf);
  if (N < M) {
    puts("0");
    return 0;
  }

  H.compute(buf, buf + N);

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