Cod sursa(job #2095140)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 26 decembrie 2017 23:44:00
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <cstdio>
#include <cstring>

using namespace std;

const int MAX_L = 2000000;

char a[MAX_L + 5], b[MAX_L + 5];
char s[2 * MAX_L + 5];
int v[2 * MAX_L + 5];

void Z(int lg) {
  int l = 0, r = 0;
  for (int i = 1; i <= lg; ++i) {
    if (i >= r) {
      int j = i;
      while (j <= lg && s[j - i] == s[j])
        j++;
      v[i] = j - i;
      l = i;
      r = j - 1;
    } else {
      int aux = v[i - l];
      int r1 = i + aux - 1;
      if (r1 >= r) {
        l = aux - 1;
        while (r <= lg && s[l] == s[r])
          l++, r++;
        v[i] = r - i;
        l = i;
        r--;
      }
    }
  }
}

int main() {
  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);

  scanf("%s %s", a, b);

  int n = strlen(a), m = strlen(b);
  for (int i = 0; i < n; ++i)
    s[i] = a[i];
  s[n] = '*';
  for (int i = n + 1; i <= n + m; ++i)
    s[i] = b[i - n - 1];

  Z(n + m);

  int ans = 0;
  for (int i = n + 1; i <= n + m; ++i)
    if (v[i] == n)
      ans++;
  printf("%d\n", ans);
  int af = 0;
  for (int i = n + 1; i <= n + m && af < 1000; ++i)
    if (v[i] == n)
      printf("%d ", i - n - 1), af++;

  return 0;
}