C ++ не может получить три, чтобы дать правильные слова для поиска - PullRequest
Новая
       47

C ++ не может получить три, чтобы дать правильные слова для поиска

0 голосов
/ 06 октября 2019

Я создаю автозаполнение интерфейса с предложением слов. Я использую три в C ++, чтобы сделать это. Я хотел бы ввести часть слова в мой код и попросить три предложить возможные слова для завершения конца моего слова. 

#include<bits/stdc++.h> 
using namespace std; 

#define alphabet (26) 

#define CHAR_TO_INDEX(c) ((int)c - (int)'a') 

struct TrieNode
{ 
    struct TrieNode *children[alphabet];

    // isWordEnd is true if the node represents
    // end of a word
    bool isWordEnd;
}; 

struct TrieNode *getNode(void) 
{ 
    struct TrieNode *Node = new TrieNode; 
    Node->isWordEnd = false; 
    for (int i = 0; i < alphabet; i++) 
        Node->children[i] = NULL; 

    return Node; 
} 

void insert(struct TrieNode *root,  const string key)
{ 
    struct TrieNode *Crawl = root;

    for (int level = 0; level < key.length(); level++)
    { 
        int index = CHAR_TO_INDEX(key[level]); 
        if (!Crawl->children[index]) 
        {
            Crawl->children[index] = getNode(); 
            //Crawl = Crawl->children[index];
        }
        Crawl = Crawl->children[index]; 
    }
    // mark last node as leaf 
    Crawl->isWordEnd = true; 
}

//returns 0 if current node has a child 
// If all children are NULL, return 1. 
bool isLastNode(struct TrieNode* root) 
{ 
    for (int i = 0; i < alphabet; i++) 
        if (root->children[i]) 
            return 0; 
    return 1; 
}


void suggestionsRec(struct TrieNode* root, string currPrefix) 
{ 
    // found a string in Trie with the given prefix 
    if (root->isWordEnd)
    {
        cout << currPrefix; 
        cout << endl;
    } 

    // All children struct node pointers are NULL 
    if (isLastNode(root)) 
    {
        //currPrefix = "help";
        //deleteNode(root);
        //delete root;
        //root = NULL;
        //currPrefix.pop_back();
        return;

    }


    for (int i = 0; i < alphabet; i++) 
    { 
        if (root->children[i]) 
        { 
            currPrefix.push_back(97 + i); 
            //currPrefix.push_back(i);
            //currPrefix.pop_back(97 + i);
             /*if (isLastNode(root)) 
             {
                currPrefix.erase(3);
             }*/


            // recur over the rest 
            suggestionsRec(root->children[i], currPrefix); 
            //printAutoSuggestions(root->children[i], currPrefix);
        } 
    } 
} 

// print suggestions for given query prefix. 
int printAutoSuggestions(TrieNode* root, const string query) 
{ 
    struct TrieNode* Crawl = root; 

    // Check if prefix is present and find the 
    // the node (of last level) with last character 
    // of given string. 
    int level; 
    int n = query.length(); 
    for (level = 0; level < n; level++) 
    { 
        int index = CHAR_TO_INDEX(query[level]); 

        // no string in the Trie has this prefix 
        if (!Crawl->children[index]) 
            return 0; 

        Crawl = Crawl->children[index]; 
    } 
    // If prefix is present as a word. 
    bool isWord = (Crawl->isWordEnd == true); 

    // If prefix is last node of tree (has no 
    // children) 
    bool isLast = isLastNode(Crawl); 

    // If prefix is present as a word, but 
    // there is no subtree below the last 
    // matching node. 
    if (isWord && isLast) 
    { 
        cout << query << endl; 
        return -1; 
    } 

    // If there are are nodes below last 
    // matching character. 
    if (!isLast) 
    { 
        string prefix = query; 
        suggestionsRec(Crawl, prefix); 
        return 1; 
    } 
} 

// Driver Code 
int main() 
{ 
    struct TrieNode* root = getNode(); 

    insert(root, "hello"); 
    insert(root, "dog"); 
    insert(root, "hell"); 
    insert(root, "cat"); 
    insert(root, "a"); 
    insert(root, "hel"); 
    insert(root, "help"); 
    insert(root, "helps"); 
    insert(root, "helping"); 

    int comp = printAutoSuggestions(root, "hel");

    if (comp == -1) 
        cout << "No other strings found with this prefix\n"; 

    else if (comp == 0) 
        cout << "No string found with this prefix\n"; 

    return 0; 
}

Когда я ввожу префикс "hel", я бы хотелсм.

hello hello hello help помогает помогает

Но вместо этого я просто вижу

hel hell hello hellp hellping hellpis

1 Ответ

0 голосов
/ 07 октября 2019

В suggestionsRec(...) у вас есть: 

for (int i = 0; i < alphabet; i++) 
  {
    currPrefix.push_back(97 + i);
    ...
    suggestionsRec(root->children[i], currPrefix); 
  }
}

Вы добавляете символы в currPrefix и сохраняете их. Таким образом, вы вызываете suggestionsRec для более поздних детей, с символами вcurrPrefix которые там не принадлежат.

...