算法设计（加权前缀搜索介绍和实现） _搜索

本文概述

C ++
Java
C#
C ++
Java

给定?字符串以及与每个字符串关联的权重。任务是找到具有给定前缀的字符串的最大权重。如果没有带给定前缀的字符串, 则打印” -1″ 。
例子：

Input : s1 = "geeks", w1 = 15 s2 = "geeksfor", w2 = 30 s3 = "srcmini", w3 = 45 prefix = geek Output : 45All the string contain the given prefix, but maximum weight of string is 45 among all.

方法1 ：(强力)
检查给定前缀的所有字符串, 如果字符串包含前缀, 则将其权重与到目前为止的最大值进行比较。
下面是上述想法的实现：
C ++

//C++ program to find the maximum weight with given prefix. //Brute Force based C++ program to find the //string with maximum weight and given prefix. #include< bits/stdc++.h> #define MAX 1000 using namespace std; //Return the maximum weight of string having //given prefix. int maxWeight( char str[MAX][MAX], int weight[], int n, char prefix[]) { int ans = -1; bool check; //Traversing all strings for ( int i = 0; i < n; i++) { check = true ; //Checking if string contain given prefix. for ( int j=0, k=0; j < strlen (str[i]) & & k < strlen (prefix); j++, k++) { if (str[i][j] != prefix[k]) { check = false ; break ; } }//If contain prefix then finding //the maximum value. if (check) ans = max(ans, weight[i]); }return ans; }//Driven program int main() { int n = 3; char str[3][MAX] = { "geeks" , "geeksfor" , "srcmini" }; int weight[] = {15, 30, 45}; char prefix[] = "geek" ; cout < < maxWeight(str, weight, n, prefix) < < endl; return 0; }

Java

//Java program to find the maximum //weight with given prefix.class GFG { static final int MAX = 1000 ; //Return the maximum weight of string having //given prefix. static int maxWeight(String str[], int weight[], int n, String prefix) { int ans = - 1 ; boolean check; //Traversing all strings for ( int i = 0 ; i < n; i++) { check = true ; //Checking if string contain given prefix. for ( int j= 0 , k= 0 ; j < str[i].length() & & k < prefix.length(); j++, k++) { if (str[i].charAt(j) != prefix.charAt(k)) { check = false ; break ; } }//If contain prefix then finding //the maximum value. if (check) ans = Math.max(ans, weight[i]); }return ans; }//Driven program public static void main(String args[]) { int n = 3 ; String str[] = { "geeks" , "geeksfor" , "srcmini" }; int weight[] = { 15 , 30 , 45 }; String prefix = "geek" ; System.out.println(maxWeight(str, weight, n, prefix)); } } //This code is contributed by Sumit Ghosh

//C# program to find the maximum weight //with given prefix. using System; class GFG {//Return the maximum weight of //string having given prefix. static int maxWeight( string []str, int []weight, int n, string prefix) { int ans = -1; bool check; //Traversing all strings for ( int i = 0; i < n; i++) { check = true ; //Checking if string contain given prefix. for ( int j=0, k=0; j < str[i].Length & & k < prefix.Length; j++, k++) { if (str[i][j] != prefix[k]) { check = false ; break ; } }//If contain prefix then finding //the maximum value. if (check) ans = Math.Max(ans, weight[i]); }return ans; }//Driver Code public static void Main() { int n = 3; String []str = { "geeks" , "geeksfor" , "srcmini" }; int []weight = {15, 30, 45}; String prefix = "geek" ; Console.WriteLine(maxWeight(str, weight, n, prefix)); } }//This code is contributed by vt_m.

输出如下：

45

方法2(有效)：
这个想法是创建和维护一个Trie。与其存储字符的普通Trie, 不如存储它的数字, 这是其前缀的最大值。当我们再次遇到前缀时, 使用现有和新的最大值来更新值。
现在, 搜索前缀以获取最大值, 从根开始搜索所有字符, 如果缺少一个字符则返回-1, 否则返回存储在根中的数字。
下面是上述想法的实现：
C ++

//C++ program to find the maximum weight //with given prefix. #include< bits/stdc++.h> #define MAX 1000 using namespace std; //Structure of a trie node struct trieNode { //Pointer its children. struct trieNode *children[26]; //To store weight of string. int weight; }; //Create and return a Trie node struct trieNode* getNode() { struct trieNode *node = new trieNode; node -> weight = INT_MIN; for ( int i = 0; i < 26; i++) node -> children[i] = NULL; }//Inserting the node in the Trie. struct trieNode* insert( char str[], int wt, int idx, struct trieNode* root) { int cur = str[idx] - 'a' ; if (!root -> children[cur]) root -> children[cur] = getNode(); //Assigning the maximum weight root-> children[cur]-> weight = max(root-> children[cur]-> weight, wt); if (idx + 1 != strlen (str)) root -> children[cur] = insert(str, wt, idx + 1, root -> children[cur]); return root; }//Search and return the maximum weight. int searchMaximum( char prefix[], struct trieNode *root) { int idx = 0, n = strlen (prefix), ans = -1; //Searching the prefix in TRie. while (idx < n) { int cur = prefix[idx] - 'a' ; //If prefix not found return -1. if (!root-> children[cur]) return -1; ans = root-> children[cur]-> weight; root = root-> children[cur]; ++idx; }return ans; }//Return the maximum weight of string having given prefix. int maxWeight( char str[MAX][MAX], int weight[], int n, char prefix[]) { struct trieNode* root = getNode(); //Inserting all string in the Trie. for ( int i = 0; i < n; i++) root = insert(str[i], weight[i], 0, root); return searchMaximum(prefix, root); }//Driven Program int main() { int n = 3; char str[3][MAX] = { "geeks" , "geeksfor" , "srcmini" }; int weight[] = {15, 30, 45}; char prefix[] = "geek" ; cout < < maxWeight(str, weight, n, prefix) < < endl; return 0; }

Java

//Java program to find the maximum weight //with given prefix.public class GFG{ static final int MAX = 1000 ; //Structure of a trie node static class TrieNode { //children TrieNode[] children = new TrieNode[ 26 ]; //To store weight of string. int weight; //constructor public TrieNode() { weight = Integer.MIN_VALUE; for ( int i = 0 ; i < 26 ; i++) children[i] = null ; } } //static TrieNode root; //Inserting the node in the Trie. static TrieNode insert(String str, int wt, int idx, TrieNode root) { int cur = str.charAt(idx) - 'a' ; if (root.children[cur] == null ) root.children[cur] = new TrieNode(); //Assigning the maximum weight root.children[cur].weight = Math.max(root.children[cur].weight, wt); if (idx + 1 != str.length()) root.children[cur] = insert(str, wt, idx + 1 , root.children[cur]); return root; }//Search and return the maximum weight. static int searchMaximum(String prefix, TrieNode root) { int idx = 0 , ans = - 1 ; int n = prefix.length(); //Searching the prefix in TRie. while (idx < n) { int cur = prefix.charAt(idx) - 'a' ; //If prefix not found return -1. if (root.children[cur] == null ) return - 1 ; ans = root.children[cur].weight; root = root.children[cur]; ++idx; }return ans; }//Return the maximum weight of string having given prefix. static int maxWeight(String str[], int weight[], int n, String prefix) { TrieNode root = new TrieNode(); //Inserting all string in the Trie. for ( int i = 0 ; i < n; i++) root = insert(str[i], weight[i], 0 , root); return searchMaximum(prefix, root); }//Driven Program public static void main(String args[]) { int n = 3 ; String str[] = { "geeks" , "geeksfor" , "srcmini" }; int weight[] = { 15 , 30 , 45 }; String prefix = "geek" ; System.out.println(maxWeight(str, weight, n, prefix)); } } //This code is contributed by Sumit Ghosh