# 算法设计：加权前缀搜索介绍和实现

## 本文概述

``````Input :
s1 = "geeks", w1 = 15
s2 = "geeksfor", w2 = 30
s3 = "srcmini", w3 = 45
prefix = geek
Output : 45

All the string contain the given prefix, but
maximum weight of string is 45 among all.``````

## 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#

``````//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``

## 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 (!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 (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``````
``45``

• 回顶