Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
2.3 kB
1
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::string str;
    str.reserve(p.size() + t.size() + 1);
    str.append(p.begin(), p.end());
    str.push_back('#');
    str.append(t.begin(), t.end());

    std::string reverse_str;
    reverse_str.reserve(p.size() + t.size() + 1);
    reverse_str.append(p.rbegin(), p.rend());
    reverse_str.push_back('#');
    reverse_str.append(t.rbegin(), t.rend());

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

    int count = 0;
    std::vector<int> data;
    data.reserve(t.size() % p.size());

    int size = p.size() - 1;

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


    return 0;
}
Leave a Comment