Алгоритм поиска с префиксами

Question

Наибольший общий префикс двух слов — это самое длинное слово, которое является началом как первого слова, так и второго. Например, слова ”хобот” и ”хорошо” имеют наибольший общий префикс ”хо”.

Наибольшие общие префиксы широко используются в поисковых технологиях, например, в подсказках при поиске. База данных содержит
N
N слов, которые нужно показывать в качестве поисковых подсказок. Стажёру было поручено проверить, входит ли введённое пользователем слово в базу данных. Стажёр реализовал поиск следующим образом: он идёт по словам из базы данных в том порядке, в котором они там записаны, и сравнивает очередное слово со словом из запроса буква за буквой, до тех пор, пока не найдутся отличающиеся буквы. Если слово из запроса совпало со словом из базы данных — поиск прекращается. Количество действий для этого алгоритма можно определить как количество слов из базы данных, с которыми проводилось сравнение, плюс сумма длин всех наибольших общих префиксов сравниваемых слов из словаря и слова из запроса.

Вам необходимо подсчитать количество действий этого алгоритма для
Q
Q различных запросов.

Формат ввода
В первой строке содержится число
N
N (
1
≤
N
≤
30000
1≤N≤30000) — количество слов в базе данных.

В каждой из следующих
N
N строк записано по одному слову. Слова состоят из прописных английских букв, их длина не превосходит 30.

В следующей строке записано число
Q
Q (
1
≤
Q
≤
30000
1≤Q≤30000) — количество запросов.

В каждой из следующих
Q
Q строк записано по одному запросу. Запросы состоят из прописных английских букв, их длина не превосходит 30.

Формат вывода
Выведите
Q
Q чисел по одному в строке — количество действий алгоритма для каждого из запросов.

Answer 1

Для решения данной задачи необходимо оптимизировать процесс поиска, поскольку прямой подход с перебором всех слов базы данных для каждого запроса будет слишком медленным при больших ограничениях (до 30,000 слов и 30,000 запросов).

Подход:

Построение Trie (префиксного дерева):
- Построим префиксное дерево (Trie) из всех слов базы данных.
- На каждом узле Trie будем хранить список индексов слов, которые проходят через этот узел (то есть имеют соответствующий префикс).
- Также будем сохранять первое вхождение каждого слова для быстрого поиска.
Обработка запросов:
- Для каждого запроса найдем индекс первого вхождения слова в базе данных (если оно есть). Если слово отсутствует, будем считать, что сравниваются все N слов.
- Затем, пройдём по префиксам запроса и для каждого префикса посчитаем количество слов в базе данных, которые имеют этот префикс и находятся до индекса K (индекс первого вхождения или N).
- Суммируем все такие количества, а также количество сравниваемых слов, чтобы получить итоговое количество действий.

Реализация:

Ниже представлен код на языке C++, реализующий описанный подход:

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

// Структура узла Trie
struct TrieNode {
    int children[26];
    vector<int> indices;
    TrieNode() {
        for(int i=0;i<26;i++) children[i]=-1;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N;
    cin >> N;
    
    // Инициализация Trie с корневым узлом
    vector<TrieNode> trie;
    trie.emplace_back(); // корень имеет индекс 0
    
    // Карта для хранения первого вхождения слова
    unordered_map<string, int> word_map;
    
    for(int i=1;i<=N;i++){
        string word;
        cin >> word;
        if(word_map.find(word) == word_map.end()){
            word_map[word] = i;
        }
        // Вставка слова в Trie
        int current = 0; // начинаем с корня
        for(char c: word){
            int c_idx = c - 'A';
            if(trie[current].children[c_idx] == -1){
                trie[current].children[c_idx] = trie.size();
                trie.emplace_back();
            }
            current = trie[current].children[c_idx];
            trie[current].indices.push_back(i);
        }
    }
    
    int Q;
    cin >> Q;
    while(Q--){
        string query;
        cin >> query;
        int K;
        auto it = word_map.find(query);
        if(it != word_map.end()){
            K = it->second;
        }
        else{
            K = N;
        }
        long long sum = 0;
        int current = 0; // начинаем с корня
        for(char c: query){
            int c_idx = c - 'A';
            if(trie[current].children[c_idx] == -1){
                break;
            }
            current = trie[current].children[c_idx];
            // Используем upper_bound для поиска количества индексов <= K
            // Так как индексы в trie[current].indices отсортированы
            int cnt = upper_bound(trie[current].indices.begin(), trie[current].indices.end(), K) - trie[current].indices.begin();
            sum += cnt;
        }
        // Количество действий: количество сравниваемых слов + сумма LCP
        cout << K + sum << "\n";
    }
}

Пояснение к коду:

Построение Trie:
- Для каждого слова из базы данных мы проходим по его символам и создаём соответствующие узлы в Trie, если они ещё не существуют.
- В каждом узле хранится список индексов слов, которые имеют данный префикс.
Обработка запросов:
- Для каждого запроса определяем K — индекс первого вхождения слова или N, если слово отсутствует.
- Проходим по символам запроса, продвигаясь по Trie.
- Для каждого префикса запроса используем upper_bound, чтобы найти количество слов с таким префиксом до индекса K.
- Суммируем все такие количества и добавляем к ним K, получая итоговое количество действий.

Сложность:

Построение Trie: O(N * L), где L — средняя длина слова (максимум 30).
Обработка запросов: O(Q * L * log(N)), так как для каждого запроса и каждого префикса выполняется бинарный поиск.

Таким образом, данный подход эффективно решает задачу в рамках заданных ограничений.

Алгоритм поиска с префиксами

问题

思考

回答

Подход:

Реализация:

Пояснение к коду:

Сложность:

分享这个问答