Untitled

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



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

    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(t.size(), 0);
    std::vector<int> suffix(t.size(), 0);
    int l = 0;
    int r = 0;

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

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

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

        if (i > 0) {
            int k = suffix[i - 1];

            while (k == p.size() || (k > 0 && t[i] != p[k])) {
                k = suffix[k - 1];
            }

            if (t[i] == p[k]) {
                ++k;
            }

            suffix[i] = k;
        }
    }


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

    int size = p.size() - 1;

    std::vector<int> data_prefix;
    data_prefix.reserve(t.size() % p.size());
    for (int i = 0; i <= (t.size() - p.size()); ++i) {
        if (prefix[i] >= size) {
            data_prefix.emplace_back(i + 1);
        }
    }

    std::vector<int> data_suffix;
    data_suffix.reserve(t.size() % p.size());
    for (int i = p.size() - 1; i < t.size(); ++i) {
        if (suffix[i] >= size) {
            data_suffix.emplace_back(i - p.size() + 2);
        }
    }

    int count{ 0 };
    std::vector<int> data;
    data.reserve(data_suffix.size() + data_prefix.size());
    // int size = p.size() - 1;

    int index_suffix = 0;
    int index_prefix = 0;

    while (index_prefix < data_prefix.size() || index_suffix < data_suffix.size()) {
        ++count;

        if (index_prefix < data_prefix.size() && index_suffix < data_suffix.size()) {
            if (data_suffix[index_suffix] <= data_prefix[index_prefix]) {
                if (data_prefix[index_prefix] == data_suffix[index_suffix]) {
                    ++index_prefix;
                }

                data.emplace_back(data_suffix[index_suffix]);
                ++index_suffix;
            } else {
                data.emplace_back(data_prefix[index_prefix]);
                 ++index_prefix;
            }

            continue;
        }

        if (index_prefix < data_prefix.size()) {
            data.emplace_back(data_prefix[index_prefix]);
            ++index_prefix;
            continue;
        }

        if (index_suffix < data_suffix.size()) {
            data.emplace_back(data_suffix[index_suffix]);
            ++index_suffix;
        }
    }

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


    return 0;
}
Leave a Comment