Рубрики

Поиск взвешенного префикса

Дано n строк и вес, связанный с каждой строкой. Задача — найти максимальный вес строки с заданным префиксом. Выведите «-1», если строка с указанным префиксом отсутствует.

Примеры:

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

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

Метод 1: (Грубая сила)

Проверьте всю строку на предмет заданного префикса, если строка содержит префикс, сравните его вес с максимальным значением.

Ниже приведена реализация вышеуказанной идеи:

C ++

// C ++ программа для поиска максимального веса с заданным префиксом.
// Программа C ++ на основе Brute Force для поиска
// строка с максимальным весом и заданным префиксом.
#include<bits/stdc++.h>
#define MAX 1000

using namespace std;

  
// Возвращаем максимальный вес строки, имеющей
// данный префикс.

int maxWeight(char str[MAX][MAX], int weight[],

                          int n, char prefix[])

{

    int ans = -1;

    bool check;

  

    // Обход всех строк

    for (int i = 0; i < n; i++)

    {

        check = true;

  

        // Проверка, содержит ли строка заданный префикс.

        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 (check)

            ans = max(ans, weight[i]);

    }

  

    return ans;

}

  
// Управляемая программа

int main()

{

    int n = 3;

    char str[3][MAX] = { "geeks", "geeksfor", "geeksforgeeks" };

    int weight[] = {15, 30, 45};

    char prefix[] = "geek";

  

    cout << maxWeight(str, weight, n, prefix) << endl;

  

    return 0;

}

Джава

// Java программа для поиска максимума
// вес с заданным префиксом.

  

class GFG {

    static final int MAX = 1000;

  

    // Возвращаем максимальный вес строки, имеющей

    // данный префикс.

    static int maxWeight(String str[], int weight[],

                              int n, String prefix)

    {

        int ans = -1;

        boolean check;

  

        // Обход всех строк

        for (int i = 0; i < n; i++)

        {

            check = true;

  

            // Проверка, содержит ли строка заданный префикс.

            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 (check)

                ans = Math.max(ans, weight[i]);

        }

  

        return ans;

    }

  

    // Управляемая программа

    public static void main(String args[])

    {

        int n = 3;

        String str[] = { "geeks", "geeksfor", "geeksforgeeks" };

        int weight[] = {15, 30, 45};

        String prefix = "geek";

  

        System.out.println(maxWeight(str, weight, n, prefix));

    }

}
// Этот код предоставлен Sumit Ghosh

C #

// C # программа для поиска максимального веса
// с заданным префиксом.

using System;

  

class GFG 

{

  

    // Возвращаем максимальный вес

    // строка с указанным префиксом.

    static int maxWeight(string []str, int []weight,

                         int n, string prefix)

    {

        int ans = -1;

        bool check;

  

        // Обход всех строк

        for (int i = 0; i < n; i++)

        {

            check = true;

  

            // Проверка, содержит ли строка заданный префикс.

            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 (check)

                ans = Math.Max(ans, weight[i]);

        }

  

        return ans;

    }

  

    // Код драйвера

    public static void Main()

    {

        int n = 3;

        String []str = {"geeks", "geeksfor",

                         "geeksforgeeks"};

        int []weight = {15, 30, 45};

        String prefix = "geek";

  

        Console.WriteLine(maxWeight(str, weight, 

                          n, prefix));

    }

}

  
// Этот код предоставлен vt_m.


Выход:

45

Метод 2 (эффективный):

Идея состоит в том, чтобы создать и поддерживать Trie. Вместо обычного Trie, где мы храним символ, сохраняем вместе с ним число, которое является максимальным значением его префикса. Когда мы сталкиваемся с префиксом, снова обновляем значение с максимальным из существующих и новых.
Теперь ищите префикс для максимального значения, пропустите символы, начиная с корня, если один из символов отсутствует, верните -1, иначе верните число, хранящееся в корне.

Ниже приведена реализация вышеуказанной идеи:

C ++

// C ++ программа для поиска максимального веса
// с заданным префиксом.
#include<bits/stdc++.h>
#define MAX 1000

using namespace std;

  
// Структура дерева узлов

struct trieNode

{

    // Указатель на своих детей.

    struct trieNode *children[26];

  

    // Для хранения веса строки.

    int weight;

};

  
// Создать и вернуть узел Trie

struct trieNode* getNode()

{

    struct trieNode *node = new trieNode;

    node -> weight = INT_MIN;

  

    for (int i = 0; i < 26; i++)

        node -> children[i] = NULL;

}

  
// Вставка узла в 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();

  

    // Назначение максимального веса

    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;

}

  
// Поиск и возврат максимального веса.

int searchMaximum(char prefix[], struct trieNode *root)

{

    int idx = 0, n = strlen(prefix), ans = -1;

  

    // Поиск префикса в TRie.

    while (idx < n)

    {

        int cur = prefix[idx] - 'a';

  

        // Если префикс не найден, вернуть -1.

        if (!root->children[cur])

            return -1;

  

        ans = root->children[cur]->weight;

        root = root->children[cur];

        ++idx;

    }

  

    return ans;

}

  
// Возвращаем максимальный вес строки с заданным префиксом.

int maxWeight(char str[MAX][MAX], int weight[], int n,

                                       char prefix[])

{

    struct trieNode* root = getNode();

  

    // Вставка всей строки в Trie.

    for (int i = 0; i < n; i++)

        root = insert(str[i], weight[i], 0, root);

  

    return searchMaximum(prefix, root);

  
}

  
// Управляемая программа

int main()

{

    int n = 3;

    char str[3][MAX] = {"geeks", "geeksfor", "geeksforgeeks"};

    int weight[] = {15, 30, 45};

    char prefix[] = "geek";

  

    cout << maxWeight(str, weight, n, prefix) << endl;

  

    return 0;

}

Джава

// Java-программа для определения максимального веса
// с заданным префиксом.

  

public class GFG{

    static final int MAX = 1000;

      

    // Структура дерева узлов

    static class TrieNode

    {

        // дети

        TrieNode[] children = new TrieNode[26];

       

        // Для хранения веса строки.

        int weight;

          

        // конструктор

        public TrieNode() {

            weight = Integer.MIN_VALUE;

            for (int i = 0; i < 26; i++)

                children[i] = null;

        }

    }

    // статический TrieNode root;

      

    // Вставка узла в 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();

       

        // Назначение максимального веса

        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;

    }

       

    // Поиск и возврат максимального веса.

    static int searchMaximum(String prefix, TrieNode root)

    {

        int idx = 0, ans = -1;

        int n = prefix.length();

       

        // Поиск префикса в TRie.

        while (idx < n)

        {

            int cur = prefix.charAt(idx) - 'a';

       

            // Если префикс не найден, вернуть -1.

            if (root.children[cur] == null)

                return -1;

       

            ans = root.children[cur].weight;

            root = root.children[cur];

            ++idx;

        }

       

        return ans;

    }

       

    // Возвращаем максимальный вес строки с заданным префиксом.

    static int maxWeight(String str[], int weight[], int n,

                                           String prefix)

    {

        TrieNode root = new TrieNode();

       

        // Вставка всей строки в Trie.

        for (int i = 0; i < n; i++)

            root = insert(str[i], weight[i], 0, root);

       

        return searchMaximum(prefix, root);

       

    }

       

    // Управляемая программа

    public static void main(String args[])

    {

        int n = 3;

        String str[] = { "geeks", "geeksfor", "geeksforgeeks" };

        int weight[] = {15, 30, 45};

        String prefix = "geek";

  

        System.out.println(maxWeight(str, weight, n, prefix));

    }

}
// Этот код предоставлен Sumit Ghosh

45

Эта статья предоставлена Anuj Chauhan . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Поиск взвешенного префикса

0.00 (0%) 0 votes