work4/work_4.2/task2.cpp - develop - novd7/algirithms_sem2

work4/work_4.2/task2.cpp
128 строк3 KB
Новиков Владимир
Рабочая тетрадь 4.2
30 май 2026, 14:10
30 май 2026, 14:100a353cb
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

const int ALPHABET_SIZE = 26;

struct TrieNode {
    TrieNode* children[ALPHABET_SIZE];
    int prefixCount;
    bool isEndOfWord;
    
    TrieNode() : prefixCount(0), isEndOfWord(false) {
        for (int i = 0; i < ALPHABET_SIZE; ++i) {
            children[i] = nullptr;
        }
    }
};

int charToIndex(char ch) {
    return ch - 'a';
}

void insert(TrieNode* root, const std::string& word) {
    TrieNode* current = root;
    for (char ch : word) {
        int index = charToIndex(ch);
        if (!current->children[index]) {
            current->children[index] = new TrieNode();
        }
        current = current->children[index];
        current->prefixCount++;
    }
    current->isEndOfWord = true;
}

int countPrefixes(TrieNode* root, const std::string& word) {
    TrieNode* current = root;
    int count = 0;
    
    for (char ch : word) {
        int index = charToIndex(ch);
        if (!current->children[index]) {
            return count;
        }
        current = current->children[index];
        if (current->isEndOfWord) {
            count++;
        }
    }
    
    return count;
}

void printPrefixes(TrieNode* root, const std::string& word) {
    TrieNode* current = root;
    std::vector<std::string> prefixes;
    
    for (size_t i = 0; i < word.length() - 1; ++i) {
        char ch = word[i];
        int index = charToIndex(ch);
        if (!current->children[index]) {
            break;
        }
        current = current->children[index];
        if (current->isEndOfWord) {
            prefixes.push_back(word.substr(0, i + 1));
        }
    }
    
    for (size_t i = 0; i < prefixes.size(); ++i) {
        std::cout << prefixes[i];
        if (i < prefixes.size() - 1) {
            std::cout << ", ";
        }
    }
}

void deleteTrie(TrieNode* node) {
    if (!node) return;
    for (int i = 0; i < ALPHABET_SIZE; ++i) {
        if (node->children[i]) {
            deleteTrie(node->children[i]);
        }
    }
    delete node;
}

std::string findWordWithMostPrefixes(const std::vector<std::string>& words) {
    TrieNode* root = new TrieNode();
    
    for (const auto& word : words) {
        insert(root, word);
    }
    
    std::string bestWord;
    int maxPrefixes = -1;
    
    for (const auto& word : words) {
        int prefixes = countPrefixes(root, word);
        if (prefixes > maxPrefixes) {
            maxPrefixes = prefixes;
            bestWord = word;
        }
    }
    
    deleteTrie(root);
    return bestWord;
}

int main() {
    std::vector<std::string> words = {"a", "ab", "abc", "abcd", "abcdef", "bcd"};
    
    std::string result = findWordWithMostPrefixes(words);
    
    std::cout << result << " (Префиксы: ";
    
    TrieNode* root = new TrieNode();
    for (const auto& word : words) {
        insert(root, word);
    }
    printPrefixes(root, result);
    deleteTrie(root);
    
    std::cout << ")" << std::endl;
    
    return 0;
}