main.cpp - master - DeC2018/0030

main.cpp
142 строки4 KB
Den
create main.cpp
07 янв 2025, 01:59
07 янв 2025, 01:597325973
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <string_view>

class Solution {
public:
    struct matcher {
        struct info { int mtindex, count; };
        std::unordered_map<std::string_view, info> dict;
        int different_word_count;

        std::vector<int> slot;
        int matching_slot_count;

        matcher(const std::vector<std::string>& words) {
            int mtind = 0;
            for (const auto& word : words) {
                auto find = dict.find(word);
                if (find != dict.end()) {
                    ++find->second.count;
                } else {
                    dict[word] = { mtind++, 1 };
                }
            }
            different_word_count = mtind;
            slot = std::vector<int>(different_word_count, 0);
            matching_slot_count = 0;
        }

        void reset() {
            for (auto& i : slot) {
                i = 0;
            }
            matching_slot_count = 0;
        }

        bool match() {
            return matching_slot_count == different_word_count;
        }

        void push(std::string_view sv) {
            auto find = dict.find(sv);
            if (find == dict.end()) return;
            if (++slot[find->second.mtindex] == find->second.count) {
                ++matching_slot_count;
            }
        }

        void pop(std::string_view sv) {
            auto find = dict.find(sv);
            if (find == dict.end()) return;
            if (--slot[find->second.mtindex] == find->second.count - 1) {
                --matching_slot_count;
            }
        }
    };

    std::vector<int> findSubstring(std::string s, const std::vector<std::string>& words) {
        int word_count = words.size();
        int word_len = words[0].size();

        matcher matcher(words);

        const char* str = s.c_str();
        int len = s.size();
        std::vector<int> ret;

        for (int off = 0; off < word_len; off++) {
            const char* beg = str + off, * end = str + len;
            if (beg + word_len * word_count <= end) {
                matcher.reset();
                for (int i = 0; i < word_count; i++) {
                    std::string_view sv(beg + i * word_len, word_len);
                    matcher.push(sv);
                }
                if (matcher.match()) {
                    ret.push_back(beg - str);
                }
                const char* pos = beg + word_len * word_count;
                while (pos + word_len <= end) {
                    std::string_view del(beg, word_len);
                    std::string_view add(pos, word_len);
                    beg += word_len;
                    pos += word_len;
                    matcher.pop(del);
                    matcher.push(add);
                    if (matcher.match()) {
                        ret.push_back(beg - str);
                    }
                }
            }
        }
        return ret;
    }
};

int main() {
    Solution solution;

    // Example 1
    std::string s1 = "barfoothefoobarman";
    std::vector<std::string> words1 = { "foo", "bar" };
    std::vector<int> result1 = solution.findSubstring(s1, words1);
    std::cout << "Example 1: [";
    for (size_t i = 0; i < result1.size(); ++i) {
        std::cout << result1[i];
        if (i < result1.size() - 1) {
            std::cout << ",";
        }
    }
    std::cout << "]" << std::endl; // Output: [0,9]

    // Example 2
    std::string s2 = "wordgoodgoodgoodbestword";
    std::vector<std::string> words2 = { "word", "good", "best", "word" };
    std::vector<int> result2 = solution.findSubstring(s2, words2);
    std::cout << "Example 2: [";
    for (size_t i = 0; i < result2.size(); ++i) {
        std::cout << result2[i];
        if (i < result2.size() - 1) {
            std::cout << ",";
        }
    }
    std::cout << "]" << std::endl; // Output: []

    // Example 3
    std::string s3 = "barfoofoobarthefoobarman";
    std::vector<std::string> words3 = { "bar", "foo", "the" };
    std::vector<int> result3 = solution.findSubstring(s3, words3);
    std::cout << "Example 3: [";
    for (size_t i = 0; i < result3.size(); ++i) {
        std::cout << result3[i];
        if (i < result3.size() - 1) {
            std::cout << ",";
        }
    }
    std::cout << "]" << std::endl; // Output: [6,9,12]

    return 0;
}