Cod sursa(job #2181575)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 21 martie 2018 19:03:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include<stdio.h>
#include<string.h>

#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

#define MAXN 2000010
#define MAXM 1000
int m[MAXM], mnr;
char *s, *p;
char phys[2 * MAXN];
int f[MAXN];
int N, M;

void prec() {
  f[0] = -1, f[1] = 0;
  for (int i = 2; i <= M; ++i) {
    int cur = f[i - 1];
    for (; cur >= 0; cur = f[cur])
      if (p[i - 1] == p[cur])
        break;
    f[i] = cur + 1;
  }
}

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() {
  freopen(InFile, "r", stdin);
  freopen(OuFile, "w", stdout);
  prec_();
  input();
  if (N == M) {
    if (!memcmp(s, p, N))
      puts("1\n0");
    else puts("0");
    return 0;
  }
  prec();
  int i = 0, j = 0;
  mnr = 0;
  for (; j < N;) {
    if (s[j] == p[i]) {
      ++i, ++j;
      if (i == M) {
        if (mnr < MAXM)
          m[mnr] = j - M;
        ++mnr;
      }
    }
    else if (i > 0)
      i = f[i];
    else ++j;
  }
  printf("%d\n", mnr);
  for (int i = 0, lim = (mnr < MAXM) ? mnr : MAXM; i < lim; ++i)
    printf("%d ", m[i]);
  puts("");
  return 0;
}