我將如何找到一個局部字匹配/查找C++

Question

我有一個拼字遊戲般的遊戲我製造麻煩。我的目標是有5個隨機字母，可能與我製作的字典中的至少一個字匹配，以便遊戲可以開始。我已經這樣做了，但是由於這5個字母是隨機的，所以它可能會匹配字典中的一個單詞。我已經完成了測試運行並獲得了隨機字母，但每次都沒有匹配（但是它的工作原理是硬編碼）。我想如果我能找到部分匹配，我可以保留組成單詞的一部分的字母，併爲那些不匹配的字母取得不同的字母。事情是，我不知道如何去做這件事。

這是我的五個隨機字母代碼：

void fiveLetters() 
{ 
    srand(time(NULL)); 

    for (int i =0; i<=4; i++) // display 5 random letters 
    { 
     int n = rand()%26; 
     char letter = (char)(n+97); 
     letters[i] = letter; 
     cout << letters[i]<< " "; 
    } 
    letters[5] = '\0'; // last value in char array null value so I can convert to string 
    attempt = letters; // the 4 letters 

    checkWords(); 
} 

用於檢查一個字匹配使用：

void checkWords() 
{ 
    if (find(words.begin(),words.end(), attempt) != words.end()) // if matches word in set 
    { 
     cout << " Words found" << endl; 
    } 
    else // if it doesn't match 
    { 
     cout << "cannot find word " << endl; 
     attempt.clear(); 
     fiveLetters(); 
    } 
} 

這本字典有很多的話然而一個文本文件因爲我只是試圖在我實現它之前讓它工作，所以我用了5-10個單詞並將它們放在一個set<string>中。對不起，長時間閱讀，任何幫助表示讚賞！

Answer 1

此實施例證明使用特里遞歸搜索加載到它的話，使用的搜索條件等可用字母的數量，最小字長度，以及「丟失」的字母的最大數目 - 被包括它們不常用的字母作爲「可用」字母。

這是特里一個26進制樹，所以每個節點有26個節點，一個字母表中的每個字母。使用單詞中的第一個字母選擇根節點的子項，第二個字母選擇此子項的其中一個子項，等等。一個節點包含一個布爾值，指示一個單詞結束爲該節點。然而，這樣的節點不是「葉子」，因爲被終止的單詞可能是較長單詞的前綴（節點終止「球」，但仍然具有「氣球」的子分支）。

線索，用遞歸搜索一起是爲特定的任務驚人地快。 （順便說一句，遞歸搜索不使用遞歸函數，它將每個級別的上下文存儲在基於向量的堆棧中）。

#include <iostream> 
#include <string> 
#include <unordered_map> 
#include <vector> 
#include <fstream> 
#include <random> 
#include <algorithm> 

class Trie { 
    // branch_count defines the number of characters which are combined to make words 
    // 26 is the number of letters, interpreted case-insensitively 
    static const int branch_count = 26; 
    // index_map takes a character and returns a number between 0 and branch_count-1 
    static int index_map(char c) { 
     if((c >= 'a') & (c <= 'z')) return c - 'a'; 
     if((c >= 'A') & (c <= 'Z')) return c - 'A'; 
     return -1; 
    } 
    // index_unmap takes an index, between 0 and branch_count-1, and returns 
    // the canonical character representation for that index 
    static char index_unmap(int index) { 
     return char('a' + index); 
    } 
    // verify_word returns true if all characters in the string map to an index 
    // returns false if at least one character is not recognized 
    static bool verify_word(const std::string& word) { 
     for(auto&& c : word) { 
      if(index_map(c) == -1) return false; 
     } 
     return true; 
    } 
    // Node is the Trie's branch_count-ary tree node class 
    struct Node { 
     Node* child_nodes[branch_count]; 
     bool terminates_word; 
     Node() : terminates_word(false) { 
      for(auto& p : child_nodes) { p = nullptr; } 
     } 
    }; 
    // make_lower(str) changes upper-case letters in str to lower-case (in-place) 
    static void make_lower(std::string& str) { 
     for(auto& c : str) { 
      if((c >= 'A') & (c <= 'Z')) { 
       c += 'a' - 'A'; 
    } } } 
    // is_space_char(x) returns true when c is some kind of 
    // unprintable or blank, but nonzero, character 
    static bool is_space_char(char c) { return (c > 0) & (c <= ' '); } 

    // trim(str) removes whitespace from the left and right sides 
    // of str (str is modified in-place) 
    static void trim(std::string& str) { 
     const auto len = str.length(); 
     if(!len) return; 
     auto i = len-1; 
     if(is_space_char(str[i])) { 
      for(--i; i+1; --i) { 
       if(!is_space_char(str[i])) { 
        str.resize(i+1); 
        break; 
     } } } 
     if(!(i+1)) { 
      str.clear(); 
      return; 
     } 
     i=0; 
     if(is_space_char(str[i])) { 
      for(++i;; ++i) { 
       if(!is_space_char(str[i])) { 
        str = str.substr(i); 
        return; 
    } } } } 
    Node *root; 
    int node_count; 
    int word_count; 

public: 
    // Trie::AddWord(word) stores a string in the Trie 
    void AddWord(std::string word) { 
     if(word.empty()) return; 
     make_lower(word); 
     if(!verify_word(word)) return; 
     Node *p = root; 
     for(const auto c : word) { 
      const int child_index = index_map(c); 
      if(child_index == -1) { 
       // verify_word(word) should have caught this. 
       // Well-behaved, but might use excess memory. 
       return; 
      } 
      Node *pchild = p->child_nodes[child_index]; 
      if(!pchild) { 
       p->child_nodes[child_index] = pchild = new Node; 
       ++node_count; 
      } 
      p = pchild; 
     } 
     if(!p->terminates_word) { 
      p->terminates_word = true; 
      ++word_count; 
    } } 

    // LoadWords(input_stream) loads all line-delimited words from 
    // the stream into the Trie 
    int LoadWords(std::istream& stream_in) { 
     const int start_count = word_count; 
     std::string line; 
     while(std::getline(stream_in, line)) { 
      trim(line); 
      AddWord(line); 
     } 
     return word_count - start_count; 
    } 
    // LoadWords(filename) loads all line-delimited words from 
    // the file at the given path 
    int LoadWords(const std::string& file_path) { 
     std::ifstream stream_in(file_path.c_str()); 
     return LoadWords(stream_in); 
    } 
    // WordCount() returns the number of words loaded so far 
    int WordCount() const { return word_count; } 

    // select_type is a helper for specifying iterator behavior 
    template <bool select_A, typename A, typename B> 
    struct select_type { typedef A type; }; 
    template <typename A, typename B> 
    struct select_type<false, A, B> { typedef B type; }; 
    template <bool select_A, typename A, typename B> 
    using select_type_t = typename select_type<select_A, A, B>::type; 

    // The iterator class is used for begin() and end(), as a minimal 
    // implementation compatible with range-based for, 
    // as well as by the destructor when destroying the 
    // tree's Node objects. 
    template <bool is_const=true, bool delete_iter=false> 
    class iterator { 
     friend class Trie; 
     typedef select_type_t<is_const, const Node*, Node*> pnode_t; 
     struct context { 
      pnode_t node; 
      int  child_index; 
     }; 
     std::vector<context> stack; 

     pnode_t advance() { 
      for(;;) { 
       if(stack.empty()) return nullptr; 
       pnode_t p = stack.back().node; 
       int &child_index = stack.back().child_index; 
       while(++child_index < branch_count) { 
        pnode_t pchild = p->child_nodes[child_index]; 
        if(pchild) { 
         stack.push_back({pchild, -1}); 
         if(!delete_iter && pchild->terminates_word) return nullptr; 
         break; 
       } } 
       if(stack.back().child_index == branch_count) { 
        stack.pop_back(); 
        if(delete_iter) return p; 
     } } } 
    public: 
     iterator(pnode_t root) { 
      stack.push_back({root, -1}); 
      if(!delete_iter) advance(); 
     } 
     iterator() {} 
     std::string operator *() const { 
      if(stack.empty()) return std::string(); 
      std::string word; 
      for(int i=0; stack[i].child_index != -1; ++i) { 
       word += index_unmap(stack[i].child_index); 
      } 
      return word; 
     } 
     iterator& operator ++() { 
      advance(); 
      return *this; 
     } 
     bool operator != (const iterator& iter) const { 
      if(stack.size() != iter.stack.size()) return true; 
      const int size = static_cast<int>(stack.size()); 
      for(int i=0; i<size; ++i) { 
       if(stack[i].node != iter.stack[i].node) return true; 
      } 
      return false; 
     } 
    }; 
    // ctor 
    Trie() : root(new Node), node_count(1), word_count(0) {} 
    // dtor 
    ~Trie() { 
     iterator<false, true> iter(root); 
     int count = 0; 
     while(auto pn = iter.advance()) { 
      delete pn; 
      ++count; 
     } 
     //std::cout << "Final word count: " << word_count << '\n'; 
     //std::cout << count << " of " << node_count << " Node objects deleted\n"; 
    } 

    // const_iterator defined from iterator with template parameter 
    // for selecting const Node pointers 
    typedef iterator<true> const_iterator; 
    const_iterator begin() const { return const_iterator(root); } 
    const_iterator end() const { return const_iterator(); } 

    // FindWords: 
    //   * takes an unordered map with char keys and int values 
    //   (counts[ch] = <how many ch may be used>) 
    //   * takes a "max_missing" count (number of substituted characters which 
    //   may be used when none remain in "counts") 
    //   * takes a "min_length", the minimum length a word 
    //   must have to be added to the results 
    std::vector<std::string> FindWords(const std::unordered_map<char, int>& counts, int max_missing=0, int min_length=0) { 
     struct context { 
      const Node*     node; 
      int       child_index; 
      std::unordered_map<char, int> counts; 
      int       missing_count; 
      bool       missing_letter; 

      context(const Node* node, const std::unordered_map<char, int>& counts, int missing_count) : 
       node(node), 
       child_index(-1), 
       counts(counts), 
       missing_count(missing_count), 
       missing_letter(false) 
      {} 
     }; 

     std::vector<context> stack; 
     stack.push_back(context(root, counts, 0)); 

     std::vector<std::string> match_list; // results are added to this 

     // This walks the tree just like the iterator's advance() function 
     // however, this function's context includes more info, like 
     // each level's available letter counts and whether a letter 
     // was used by taking one of the available "missing" letters. 
     while(!stack.empty()) { 
      context& ctx = stack.back(); 
      while(++ctx.child_index < branch_count) { 
       const Node* pchild = ctx.node->child_nodes[ctx.child_index]; 
       if(!pchild) continue; 
       const char c = index_unmap(ctx.child_index); 
       if(ctx.counts[c] > 0) { 
        ctx.missing_letter = false; 
        context child_ctx(pchild, ctx.counts, ctx.missing_count); 
        --child_ctx.counts[c]; 
        stack.push_back(child_ctx); // ctx made invalid here 
        break; 
       } 
       else if(ctx.missing_count < max_missing) { 
        ctx.missing_letter = true; 
        context child_ctx(pchild, ctx.counts, ctx.missing_count + 1); 
        stack.push_back(child_ctx); // ctx made invalid here 
        break; 
      } } 
      context& fresh_ctx = stack.back(); 
      if(fresh_ctx.child_index == branch_count) { 
       stack.pop_back(); 
       continue; 
      } 
      // After a new level is pushed on the stack, check if the last node 
      // completes a word from the tree, then check various conditions 
      // required for adding it to the results. 
      if(static_cast<int>(stack.size()) > min_length && fresh_ctx.node->terminates_word) { 
       std::string word; 
       for(const auto& entry : stack) { 
        if(entry.child_index != -1) { 
         char c = index_unmap(entry.child_index); 
         if(entry.missing_letter) { 
          // modify the character to show it was substituted 
          if(c >= 'a' && c <= 'z') { 
           // capitalize missing lower-case letters 
           word += c + 'A' - 'a'; 
          } else { 
           // put funky square brackets around other types of missing characters 
           word += '['; 
           word += c; 
           word += ']'; 
          } 
         } else { 
          word += c; 
       } } } 
       match_list.push_back(word); 
     } } 
     return match_list; 
    } 

    // FindWords(letters, max_missing, min_length) creates a "counts" map 
    // from the "letters" string and uses it to call FindWords(counts...) 
    std::vector<std::string> FindWords(std::string letters, int max_missing=0, int min_length=0) { 
     std::unordered_map<char, int> counts; 
     for(auto c : letters) { 
      switch(c) { 
       case '?': ++max_missing; break; // '?' is a wildcard (blank tile) 
       default: ++counts[c]; break; 
     } } 
     return FindWords(counts, max_missing, min_length); 
    } 

    // DumpAllWords dumps all words contained in the Trie to cout (in alphabetical order) 
    void DumpAllWords() { 
     for(auto&& s : *this) { 
      std::cout << s << '\n'; 
    } } 
}; 

class DrawPool { 
    std::mt19937 rng; 
    std::string letters; 
    int last_count = 1; 
    struct arg_is_int { char i[4]; }; 
    static arg_is_int argtype(int); 
    static char  argtype(char); 
    void Add() {} 
    template <typename T, typename ...Args> 
    void Add(T arg, Args ...args) { 
     if(sizeof(argtype(arg)) == sizeof(arg_is_int)) { 
      last_count = arg; 
     } else { 
      letters += std::string(last_count, arg); 
     } 
     Add(args...); 
    } 

public: 
    void Shuffle() { 
     letters.clear(); 
     Add(2, '?', 
      12,'e', 9, 'a', 'i', 8, 'o', 6, 'n', 'r', 't', 
      4, 'l', 's', 'u', 'd', 3, 'g', 
      2, 'b', 'c', 'm', 'p', 'f', 'h', 'v', 'w', 'y', 
      1, 'k', 'j', 'x', 'q', 'z'); 
     std::shuffle(letters.begin(), letters.end(), rng); 
    } 
    int Count() const { return static_cast<int>(letters.length()); } 
    std::string Get(int count) { 
     if(count > Count()) count = Count(); 
     const std::string draw = letters.substr(0, count); 
     letters.erase(0, count); 
     return draw; 
    } 

    DrawPool() { 
     std::random_device rd; 
     std::seed_seq seed = {rd(), rd(), rd(), rd(), rd()}; 
     rng.seed(seed); 
     Shuffle(); 
    } 
}; 

int main() { 
    Trie trie; 

    // Call trie.LoadWords(filename) with each filename in the list 
    // The names here are files from the SCOWL word lists. 
    // These may be replaced with your own file name(s). 
    for(auto s : { 
     "english-words.10", 
     "english-words.20", 
     "english-words.35", 
     "english-words.40", 
     "english-words.50", 
     "english-words.55", 
     "english-words.60", 
     "english-words.70", 
     "english-words.80", 
     "english-words.95" 
    }) { 
     int count = trie.LoadWords(s); 
     std::cout << "Loaded " << count << " new words from " << s << '\n'; 
    } 
    std::cout << "\nLoaded a total of " << trie.WordCount() << " words\n"; 

    //trie.DumpAllWords(); // send all words to cout 

    // match a set of 7 randomly-drawn letters 
    // draw one more letter each time no matches found 
    DrawPool draw_pool; 
    std::string rack; 
    std::vector<std::string> word_list; 
    do { 
     rack += draw_pool.Get(rack.empty() ? 7 : 1); 
     std::cout << "\nRack: " << rack << '\n'; 
     // find words at least 3 letters long, using the letters 
     // from "rack". The only "missing" matches allowed are 
     // 1 for each wildcard ('?') in "rack". 
     word_list = trie.FindWords(rack, 0, 3); 
    } while(word_list.empty() && draw_pool.Count()); 

    // Dump the results to cout 
    std::cout << "\nFound " << word_list.size() << " matches\n"; 
    for(auto&& word : word_list) { 
     std::cout << " " << word << '\n'; 
    } 
}