Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
4.1 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);

    // char ch;
    // std::string str;
    // str.reserve(2000001);

    // size_t psize = 0;

    // while (std::cin.get(ch)) {
    //     if (ch == '\n') {
    //         str.push_back('#');
    //         break;
    //     }

    //     str.push_back(ch);
    //     ++psize;
    // }

    // std::string reverse_str;
    // reverse_str.reserve(2000001);
    // int index = psize - 1;
    // size_t tsize = 0;

    // while (std::cin.get(ch)) {
    //     if (index >= 0) {
    //         reverse_str.push_back(str[index]);
    //         --index;
    //     }

    //     if (ch == '\n') {
    //         break;
    //     }

    //     str.push_back(ch);
    //     ++tsize;
    // }

    // index = str.size() - 1;
    // reverse_str.push_back('#');

    // while (index > psize) {
    //     reverse_str.push_back(str[index]);
    //     --index;
    // }


    // // std::string t = "Caaabdaaaa";
    // // std::string p = "aaaa";

    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> prefix(str.size(), 0);
    // std::vector<int> suffix(reverse_str.size(), 0);
    // int left = 0;
    // int right = 0;
    // int reverse_left = 0;
    // int reverse_right = 0;


    // for (int i = 1; i < str.size(); ++i) {
    //     if (i <= right) {
    //         prefix[i] = std::min(right - i + 1, prefix[i - left]);
    //     }

    //     while (i + prefix[i] < str.size() && str[prefix[i]] == str[i + prefix[i]]) {
    //         ++prefix[i];
    //     }

    //     if (i + prefix[i] - 1 > right) {
    //         right = i + prefix[i] - 1;
    //         left = i;
    //     }


    //     if (i <= reverse_right) {
    //         suffix[i] = std::min(reverse_right - i + 1, suffix[i - reverse_left]);
    //     }

    //     while (i + suffix[i] < reverse_str.size() && reverse_str[suffix[i]] == reverse_str[i + suffix[i]]) {
    //         ++suffix[i];
    //     }

    //     if (i + suffix[i] - 1 > reverse_right) {
    //         reverse_right = i + suffix[i] - 1;
    //         reverse_left = i;
    //     }
    // }

    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)
            //|| (prefix[i] + suffix[str.size() - i + prefix[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