Cod sursa(job #1889521)

Utilizator danalex97Dan H Alexandru danalex97 Data 22 februarie 2017 19:17:55
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

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

const int N = 2000010;

int n, m, p[N];
string a, b;

// p[i] = the length of the longest suffix from position i that overlaps
// over the longest prefix of the array a

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

  p[1] = 0;
  int k = 0; // the current match size
  for (int q = 2; q <= n; ++q) {
    while (a[q - 1] != a[k] && k > 0) {
      k = p[k]; // if the next char does not match, we the first smaller longest
      // prefix
    }

    if (a[q - 1] == a[k]) {
      ++k;
    }

    p[q] = k;
  }

  k = 0;
  int ans = 0;
  vector<int> v;
  for (int q = 0; q < m; ++q) {
    while (b[q - 1] != a[k] && k > 0) {
      k = p[k];
    }
    if (b[q - 1] == a[k]) {
      ++k;
    }
    // cout << b[q - 1] << ' ' << k << '\n';

    if (k == n) {
      ++ans;
      if (v.size() < 1000) {
        v.push_back(q);
      }
    }
  }

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