Cod sursa(job #1889758)

Utilizator danalex97Dan H Alexandru danalex97 Data 22 februarie 2017 21:13:34
Problema Potrivirea sirurilor Scor 6
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

ifstream F("strmatch.in");
ofstream G("strmatch.out");

const int N = 2000010;

string a, b;

// both tables are 0-indexed
int bcr[26], gsr[N], f[N], n, m;

void build_bcd() {
  for (int i = 0; i < n; ++i) {
    bcr[a[i] - int('A')] = i;
  }
}

void build_gsr() {
  // f[i] = biggest suffix that matches over the end of the array
  f[n] = n + 1;
  int k = n;
  for (int i = n - 1; i >= 0; --i) {
    //cerr << i << ' ' << k << '\n';
    while (a[i] != a[k] && k < n) {
      //cerr << k << '\n';
      // update the shifts while i move
      if (gsr[k] == 0) {
        gsr[k] = k - i;
      }

      // move to right like at KMP
      k = f[k + 1] - 1;
      //break;
    }
    f[i] = k;
    --k;
  }

  // the other case is matching on the beginning of the array
  // the values is f[0]; if i arrive at the place of f[0], the values should
  // decrease as I am maching the smallest part of array

  k = f[0];
  for (int i = 0; i <= m; ++i) {
    // this stuff for all cause we want to align the things
    if (gsr[i] == 0) {
      gsr[i] = k;
    }
    if (i == k) {
      // the rightmost thing is this one, not the other one
      k = f[k];
    }
  }
}

int main() {
  F >> a >> b;
  n = a.size();
  m = b.size();

  build_bcd();
  build_gsr();

  int i = 0, k = 0;
  int ans = 0;
  vector<int> v;
  while (i <= m - n) {
    //cout << i << '\n';
    k = n - 1;
    while (k >= 0 && a[k] == b[i + k]) {
      k--;
    }
    if (k < 0) {
      ans ++;
      v.push_back(i);
      i += gsr[0];
    }
    else
      i += max(gsr[k + 1], k - bcr[b[i + k] - int('A')] + 1);
  }

  G << ans << '\n';
  for (auto x : v) {
    G << x << ' ';
  }
  G << '\n';
}