Cod sursa(job #2295659)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 3 decembrie 2018 20:36:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include<cstdio>
#include<cstring>
typedef unsigned long long hsh;

#ifdef INFOARENA
#define ProblemName "strmatch"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

const int MAXN = 2000001;
const int MAXM = 1000;
int m[MAXM], mnr;
char buf[MAXN];
int N, M;
const int B = 29;

int main() {
  freopen(InFile, "r", stdin);
  freopen(OuFile, "w", stdout);
  scanf("%s", buf);
  M = strlen(buf);
  hsh BlaM = 1;
  for (int i = 1; i <= M; ++i)
    BlaM *= B;
  hsh H = 0;
  for (int i = 0; i < M; ++i)
    H = H * B + buf[i];
  scanf("%s", buf);
  N = strlen(buf);
  if (N < M) {
    puts("0");
    return 0;
  }
  hsh curH = 0;
  for (int i = 0; i < M; ++i)
    curH = curH * B + buf[i];
  for (int i = M;; ++i) {
    if (curH == H) {
      if (mnr < MAXM)
        m[mnr] = i - M;
      ++mnr;
    }
    if (i == N)
      break;
    curH = curH * B + buf[i] - buf[i - M] * BlaM;
  }
  printf("%d\n", mnr);
  for (int i = 0, lim = (mnr < MAXM) ? mnr : MAXM; i < lim; ++i)
    printf("%d ", m[i]);
  puts("");
  return 0;
}