Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.9 kB
1
Indexable
Never
#include <algorithm>
#include <ios>
#include <iostream>
#include <string>
#include <vector>

inline std::vector<int> zfunction(const std::string &str) {
  int size = str.size();
  std::vector<int> data(size, 0);

  for (int i = 1, l = 0, r = 0; i < size; ++i) {
    if (i <= r) {
      data[i] = std::min(r - i + 1, data[i - l]);
    }

    while (i + data[i] < size && str[data[i]] == str[i + data[i]]) {
      ++data[i];
    }

    if (i + data[i] - 1 > r) {
      l = i;
      r = i + data[i] - 1;
    }
  }

  return data;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::string p;
  p.reserve(1000001);
  std::getline(std::cin, p);

  int psize = p.size();

  std::string str;
  str.reserve(2000003);

  std::string reverse_str;
  reverse_str.reserve(2000003);

  str.append(p);
  str.push_back('#');

  std::reverse(p.begin(), p.end());
  reverse_str.append(p);
  reverse_str.push_back('#');

  std::getline(std::cin, p);

  int tsize = p.size();
  str.append(p);

  if (psize > tsize) {
    std::cout << 0 << "\n";
    return 0;
  }

  std::reverse(p.begin(), p.end());
  reverse_str.append(p);

  auto prefix = zfunction(str);
  auto suffix = zfunction(reverse_str);

  std::vector<int> data;
  data.reserve(tsize - psize);

  int min_size = psize - 1;
  int terminator = prefix.size() - psize;

  for (int i = psize + 1, end = terminator + 1; i <= end; ++i) {
    if (prefix[i] == psize || (prefix[i] == min_size && i <= terminator) ||
        (prefix[i] == 0 && i <= terminator &&
         suffix[str.size() - i + 1] == min_size) ||
        (i <= terminator &&
         prefix[i] + suffix[str.size() - i + 1] == min_size)) {
      data.emplace_back(i - psize);
    }
  }

  std::cout << data.size() << "\n";
  for (const auto &pos : data) {
    std::cout << pos << " ";
  }
  std::cout << "\n";

  return 0;
}
Leave a Comment