Dado un conjunto de strings S y una string P , la tarea es imprimir todas las strings del conjunto con el sufijo P. Ejemplos:
Entrada: S = {“geeks”, “geeksforgeeks”, “geek”, “newgeeks”, “friendsongeeks”, “toppergeek”} P = “geeks” Salida: geeks friendsongeeks geeksforgeeks newgeeks Entrada: S = {“wideworld”, “ webworld”, “classicword”, “world”, “worldclass”} P = “world” Salida: wideworld webworld world
Enfoque: La idea es utilizar la búsqueda de patrones utilizando un Trie de todos los sufijos .
- Guarde las cuerdas en un Trie en orden inverso.
- Invierta la string P y búsquela usando el algoritmo de búsqueda Trie estándar .
- Verifique si la string invertida P es en sí misma una palabra en Trie, que se verifica al ver si el último Node coincidente tiene establecido el indicador isEndWord .
- De lo contrario, si la string invertida P forma un sufijo, imprima recursivamente todos los Nodes debajo del subárbol del último Node coincidente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to print all // strings from a given set // with suffix P #include <bits/stdc++.h> using namespace std; #define CHILD (26) // Converts key current character // into index use only 'a' through // 'z' and lower case #define CHAR_TO_INDEX(c) (int)(c - 'a') // Trie node struct TrieNode { struct TrieNode* children[CHILD]; // isWordEnd is true if the node // represents end of a word bool isWordEnd; }; // Function to reverse a string string reverseStr(string str) { int n = str.length(); // Swap character starting from // two corners for (int i = 0; i < n / 2; i++) swap(str[i], str[n - i - 1]); return str; } // Returns new trie node struct TrieNode* getNode(void) { struct TrieNode* pNode = new TrieNode; pNode->isWordEnd = false; for (int i = 0; i < CHILD; i++) pNode->children[i] = NULL; return pNode; } // If not present, inserts key into // trie. If the key is suffix of trie // node, just mark leaf node void insert(struct TrieNode* root, const string key) { struct TrieNode* pCrawl = root; for (int level = 0; level < key.length(); level++) { int index = CHAR_TO_INDEX(key[level]); if (!pCrawl->children[index]) pCrawl->children[index] = getNode(); pCrawl = pCrawl->children[index]; } // Mark last node as leaf pCrawl->isWordEnd = true; } // Returns true if key presents in // the trie, else false bool search(struct TrieNode* root, const string key) { int length = key.length(); struct TrieNode* pCrawl = root; for (int level = 0; level < length; level++) { int index = CHAR_TO_INDEX(key[level]); if (!pCrawl->children[index]) return false; pCrawl = pCrawl->children[index]; } return (pCrawl != NULL && pCrawl->isWordEnd); } // 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 < CHILD; i++) if (root->children[i]) return 0; return 1; } // Recursive function to print strings // having given suffix void printStrings(struct TrieNode* root, string currsuffix) { // If a string with currsuffix // is found if (root->isWordEnd) { cout << reverseStr(currsuffix); cout << endl; reverseStr(currsuffix); } // All children struct node // pointers are NULL if (isLastNode(root)) return; for (int i = 0; i < CHILD; i++) { if (root->children[i]) { // Append current character // to currsuffix string currsuffix.push_back(97 + i); // recur over the rest printStrings(root->children[i], currsuffix); // remove last character currsuffix.pop_back(); } } } // print strings with given suffix int printStringsWithGivenSuffix( TrieNode* root, const string query) { struct TrieNode* pCrawl = root; // Check if suffix is present // and find 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 suffix if (!pCrawl->children[index]) return 0; pCrawl = pCrawl->children[index]; } // If suffix is present as a word. bool isWord = (pCrawl->isWordEnd == true); // If suffix is last node of // tree (has no children) bool isLast = isLastNode(pCrawl); // If suffix 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 nodes below // last matching character. if (!isLast) { string suffix = query; printStrings(pCrawl, suffix); return 1; } } // Driver Code int main() { struct TrieNode* root = getNode(); vector<string> S = { "geeks", "geeksforgeeks", "geek", "newgeeks", "friendsongeeks", "toppergeek" }; for (string str : S) { insert(root, reverseStr(str)); } string P = "eek"; printStringsWithGivenSuffix( root, reverseStr(P)); return 0; }
Python
# Python3 code for the above program class TrieNode(): def __init__(self): # Initialize one node for trie self.children = {} self.last = False def reverse(s): str = "" for i in s: str = i + str return str class Trie(): def __init__(self): # Initialize the trie structure self.root = TrieNode() self.word_list = [] def formTrie(self, keys): # Forms a trie structure # with the given set of # strings if it does not # exists already else it # merges the key into it # by extending the # structure as required for key in keys: # inserting one key # to the trie. self.insert(key) def insert(self, key): # Inserts a key into # trie if it does not # exist already. And if # the key is a suffix # of the trie node, just # marks it as leaf node. node = self.root for a in list(key): if not node.children.get(a): node.children[a] = TrieNode() node = node.children[a] node.last = True def search(self, key): # Searches the given key # in trie for a full match # and returns True on # success else returns False node = self.root found = True for a in list(key): if not node.children.get(a): found = False break node = node.children[a] return node and node.last and found def printStrings(self, node, word): # Method to recursively # traverse the trie # and return a whole word if node.last: self.word_list.append(word) for a, n in node.children.items(): self.printStrings(n, word + a) def printStringsWithGivenSuffix(self, key): # Returns all the words in # the trie whose common # suffix is the given key # thus listing out all # the strings node = self.root not_found = False temp_word = '' for a in list(key): if not node.children.get(a): not_found = True break temp_word += a node = node.children[a] if not_found: return 0 elif node.last and not node.children: return -1 self.printStrings(node, temp_word) for s in self.word_list: print(reverse(s)) return 1 # Driver Code # keys to form the trie structure keys = [reverse("geeks"), reverse("geeksforgeeks"), reverse("geek"), reverse("newgeeks"), reverse("friendsongeeks"), reverse("toppergeek")] # key key = "eek" status = ["Not found", "Found"] # creating trie object t = Trie() # creating the trie structure # with the given set of strings t.formTrie(keys) # print string having suffix 'P' # our trie structure comp = t.printStringsWithGivenSuffix(reverse(key))
Producción:
geek toppergeek
s
Publicación traducida automáticamente
Artículo escrito por MohammadMudassir y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA