Untitled

mail@pastecode.io avatar
unknown
plain_text
22 days ago
3.3 kB
1
Indexable
Never
#include <algorithm>
#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;
    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);


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

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

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

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

        if (prefix[i] == psize || (prefix[i] == min_size && i < terminator)
            || (skip_index < suffix.size() && prefix[i] + suffix[skip_index] >= 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