Cod sursa(job #2279075)

Utilizator palomaPaloma Josse paloma Data 8 noiembrie 2018 21:23:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fi("strmatch.in");
ofstream fo("strmatch.out");

const int maxn = 2 * 1e6;
const int maxr = 1000;

char a[maxn + 2], b[maxn + 2];
int n, m, ans, pi[maxn + 1], pos[maxr + 1];

int main()
{
  fi >> (a + 1) >> (b + 1);

  int k;
  n = strlen(a + 1);
  m = strlen(b + 1);
  pi[ 1 ] = 0;
  k = 0;
  for (int i = 2; i <= n; i++) {
    while (k && a[k + 1] != a[ i ])
      k = pi[ k ];
    if (a[k + 1] == a[ i ])
      k++;
    pi[ i ] = k;
  }

  k = 0;
  for (int i = 1; i <= m; i++) {
    while (k && a[k + 1] != b[ i ])
      k = pi[ k ];
    if (a[k + 1] == b[ i ])
      k++;
    if (k == n) {
      ans++;
      if (ans <= maxr)
        pos[ans] = i;
    }
  }

  fo << ans << '\n';
  for (int i = 1; i <= min(ans, maxr); i++) {
    fo << pos[ i ] - n << ' ';
  }

  fo.close();
  fi.close();

  return 0;
}