Untitled

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



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 p;
    // std::getline(std::cin, p);

    // std::string t;
    // std::getline(std::cin, t);

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


    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;
        }
    }


    // for (int i = 0; i < prefix.size(); ++i) {
    //     std::cout << prefix[i] << " ";
    // }
    // std::cout << "\n";

    // for (int i = 0; i < suffix.size(); ++i) {
    //     std::cout << suffix[i] << " ";
    // }
    // std::cout << "\n";

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

    int min_size = psize - 1;

    for (int i = psize + 1, end = prefix.size() - psize; i <= end; ++i) {
        int skip_index = str.size() - i + prefix[i] + 1;

        if (prefix[i] == psize || prefix[i] == min_size
            || (skip_index < suffix.size() && prefix[i] + suffix[skip_index] == min_size)) {
            data.emplace_back(i - psize - 1);
            ++count;
        }
    }
    
    std::cout << count << "\n";
    for (const auto& pos : data) {
        std::cout << pos << " ";
    }
    std::cout << "\n";


    return 0;
}
Leave a Comment