C++何もわからない

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <string>
#include <memory>

class PatriciaNode {
public:
    std::unordered_map<char, std::unique_ptr<PatriciaNode>> children;
    PatriciaNode* fail;
    bool is_output;
    std::string prefix;

    PatriciaNode() : fail(nullptr), is_output(false) {}
};

class PatriciaAhoCorasick {
private:
    std::unique_ptr<PatriciaNode> root;

public:
    PatriciaAhoCorasick() : root(std::make_unique<PatriciaNode>()) {}

    void addPattern(const std::string& pattern) {
        PatriciaNode* node = root.get();
        size_t i = 0;
        while (i < pattern.length()) {
            auto it = node->children.find(pattern[i]);
            if (it == node->children.end()) {
                auto newNode = std::make_unique<PatriciaNode>();
                newNode->prefix = pattern.substr(i);
                node->children[pattern[i]] = std::move(newNode);
                node = node->children[pattern[i]].get();
                break;
            } else {
                PatriciaNode* child = it->second.get();
                size_t j = 0;
                while (j < child->prefix.length() && i < pattern.length() && child->prefix[j] == pattern[i]) {
                    ++i;
                    ++j;
                }
                if (j == child->prefix.length()) {
                    node = child;
                } else {
                    // 分割が必要
                    auto splitNode = std::make_unique<PatriciaNode>();
                    splitNode->prefix = child->prefix.substr(0, j);
                    child->prefix = child->prefix.substr(j);
                    splitNode->children[child->prefix[0]] = std::move(it->second);
                    node->children[splitNode->prefix[0]] = std::move(splitNode);
                    node = node->children[splitNode->prefix[0]].get();
                    if (i < pattern.length()) {
                        auto newNode = std::make_unique<PatriciaNode>();
                        newNode->prefix = pattern.substr(i);
                        node->children[newNode->prefix[0]] = std::move(newNode);
                    }
                    break;
                }
            }
        }
        node->is_output = true;
    }

    void buildFailTransitions() {
        std::queue<PatriciaNode*> q;
        root->fail = root.get();
        for (auto& pair : root->children) {
            pair.second->fail = root.get();
            q.push(pair.second.get());
        }

        while (!q.empty()) {
            PatriciaNode* current = q.front();
            q.pop();

            for (auto& pair : current->children) {
                char ch = pair.first;
                PatriciaNode* child = pair.second.get();
                PatriciaNode* fail = current->fail;

                while (fail != root.get() && fail->children.find(ch) == fail->children.end()) {
                    fail = fail->fail;
                }

                if (fail->children.find(ch) != fail->children.end()) {
                    child->fail = fail->children[ch].get();
                } else {
                    child->fail = root.get();
                }

                child->is_output |= child->fail->is_output;
                q.push(child);
            }
        }
    }

    bool search(const std::string& text) {
        PatriciaNode* current = root.get();
        size_t i = 0;

        while (i < text.length()) {
            auto it = current->children.find(text[i]);
            if (it != current->children.end()) {
                PatriciaNode* child = it->second.get();
                size_t j = 0;
                while (j < child->prefix.length() && i < text.length() && child->prefix[j] == text[i]) {
                    ++i;
                    ++j;
                }
                if (j == child->prefix.length()) {
                    current = child;
                    if (current->is_output) {
                        return true;  // マッチしたらすぐに true を返す
                    }
                } else {
                    i -= j;
                    current = root.get();
                }
            } else {
                if (current == root.get()) {
                    ++i;
                } else {
                    current = current->fail;
                }
            }
        }
        return false;  // マッチがなければ false を返す
    }
};

class FilePathFilter {
private:
    PatriciaAhoCorasick ac;

public:
    FilePathFilter(const std::vector<std::string>& filterPatterns) {
        for (const auto& pattern : filterPatterns) {
            ac.addPattern(pattern);
        }
        ac.buildFailTransitions();
    }

    bool contains(const std::string& filePath) {
        return ac.search(filePath);
    }
};

int main() {
    std::vector<std::string> filters = {"documents", "downloads", ".txt"};
    std::vector<std::string> filePaths = {
        "/home/user/documents/file1.txt",
        "/home/user/downloads/file2.pdf",
        "/home/user/pictures/image.jpg"
    };

    FilePathFilter pathFilter(filters);

    for (const auto& path : filePaths) {
        if (pathFilter.contains(path)) {
            std::cout << "File path " << path << " matches a filter." << std::endl;
        } else {
            std::cout << "File path " << path << " does not match any filter." << std::endl;
        }
    }

    return 0;
}

void addPattern(const std::string& pattern) {
    PatriciaNode* node = root.get();
    size_t i = 0;

    while (i < pattern.length()) {
        auto it = node->children.find(pattern[i]);
        if (it == node->children.end()) {
            // 新しいノードを作成し、パターンの残りを追加
            auto newNode = std::make_unique<PatriciaNode>();
            newNode->prefix = pattern.substr(i);
            node->children[pattern[i]] = std::move(newNode);
            break;
        } else {
            // 既存のノードとプレフィックスのマッチング
            PatriciaNode* child = it->second.get();
            auto [prefixMismatch, textMismatch] = std::ranges::mismatch(child->prefix, pattern.substr(i));

            if (prefixMismatch == child->prefix.end()) {
                // プレフィックスが完全に一致する場合
                if (textMismatch == pattern.substr(i).end()) {
                    // パターンが完全に一致する場合
                    child->is_pattern_end = true;  // 現在のノードを終端とする
                    break;
                } else {
                    // ノードを更新し、次の文字に進む
                    node = child;
                    i += node->prefix.length(); // 既に一致した部分をスキップ
                }
            } else {
                // プレフィックスが部分一致する場合、分割が必要
                auto splitNode = std::make_unique<PatriciaNode>();
                splitNode->prefix = child->prefix.substr(0, std::distance(child->prefix.begin(), prefixMismatch));
                splitNode->is_pattern_end = false;  // 分割時に前方ノードを false に設定
                child->prefix = child->prefix.substr(std::distance(child->prefix.begin(), prefixMismatch));
                splitNode->children[child->prefix[0]] = std::move(it->second);
                node->children[splitNode->prefix[0]] = std::move(splitNode);
                node = node->children[splitNode->prefix[0]].get();
                
                if (textMismatch != pattern.substr(i).end()) {
                    auto newNode = std::make_unique<PatriciaNode>();
                    newNode->prefix = pattern.substr(std::distance(pattern.begin(), textMismatch));
                    node->children[newNode->prefix[0]] = std::move(newNode);
                }
                break;
            }
        }
    }
}

void buildFailTransitions() {
    std::queue<PatriciaNode*> q;
    root->fail = std::nullopt; // ルートノードのフェイル遷移先はnullopt
    q.push(root.get()); // ルートノードそのものをキューに追加

    while (!q.empty()) {
        PatriciaNode* current = q.front();
        q.pop();

        for (auto& pair : current->children) {
            PatriciaNode* child = pair.second.get();
            std::optional<PatriciaNode*> fail = current->fail;

            // fail チェーンを辿って適切なフェイル遷移先を探す
            while (fail.has_value()) { // ルートノードのフェイル遷移のばあいのみループに入らない
                PatriciaNode* fail_node = *fail;
                if (fail_node->children.contains(child->prefix[0])) {
                    PatriciaNode* node = fail_node->children[child->prefix[0]].get();
                    if (child->prefix.starts_with(node->prefix)) {
                        child->fail = node;
                        break;
                    }
                }
                fail = fail_node->fail;
            }

            // 適切なフェイル遷移先が見つからない場合、ルートを設定
            if (!child->fail.has_value()) {
                child->fail = root.get();
            }

            q.push(child); // 子ノードをキューに追加
        }
    }
}

bool search(const std::string& text) {
    PatriciaNode* current = root.get();
    size_t i = 0;

    while (i < text.length()) {
        auto it = current->children.find(text[i]);
        if (it != current->children.end()) {
            PatriciaNode* child = it->second.get();
            // 現在のノードのプレフィックスをマッチング
            if (text.substr(i).starts_with(child->prefix)) {
                i += child->prefix.length();
                current = child;
                if (current->is_pattern_end && i == text.length()) {
                    return true;  // 完全なパターンマッチかつ文字列の終端の場合のみ true を返す
                }
                continue;
            } 
        }

        // マッチしなかった場合、現在の位置を戻す
        if (current == root.get()) {
            ++i;
        } else {
            current = current->fail;
        }
    }
    return false;
}