Попытки — это одна из структур данных, используемых при манипуляциях со строками. Он используется в ситуациях, когда извлекают строки на основе префикса. Например: поисковые системы
В попытках строки хранятся в виде деревьев символов. Ссылки создаются в соответствии с тем, как они появляются в каждой строке.
Следующее дерево (trie) строится путем хранения строк,
их, там, ответь, любой, пока
< root >
/ \ \
t a b
| | |
h n y
| | \ |
e s y e
/ | |
i r w
| | |
r e e
|
r
Временная сложность для вставки/поиска: O(word_length)
Пространственная сложность:O(ALPHABET_SIZE * длина_слова * количество_слов)
Ниже приведен пример кода Java, показывающий, как работает алгоритм.
Три операции: «добавить», «префикс» и «слово».
Добавление слова «рыба» в словарь:
add fish
Найдите в словаре слова с приставкой «собака»:
prefix dog
Узнайте, как слова с названием «кошка» могут быть вставлены в словарь:
word cat
- Реализация будет работать только с диапазоном символов [a-z]
import java.util.Arrays;
import java.util.Scanner;
public class Dictoinary {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
Tries tries = new Tries();
for (int a0 = 0; a0 < n; a0++) {
String op = in.next();
String contact = in.next();
if ("add".equals(op)) {
tries.addWord(tries.root, contact);
} else if ("prefix".equals(op)) {
System.out.println(tries.countPrefixes(tries.root, contact));
} else if ("word".equals(op)) {
System.out.println(tries.countWords(tries.root, contact));
} else {
System.out.println("Invalid operation: " + op);
}
}
}
}
class Tries {
Vertex root = new Vertex();
void addWord(Vertex vertex, String word) {
if (word.isEmpty()) {
vertex.words++;
// word itself is also considered as a prefix
vertex.prefixes++;
} else {
vertex.prefixes++;
char firstChar = word.charAt(0);
if (vertex.edges[firstChar - 97] == null) {
vertex.edges[firstChar - 97] = new Vertex();
}
addWord(vertex.edges[firstChar - 97], word.substring(1));
}
}
int countWords(Vertex vertex, String word) {
if (word.isEmpty()) {
return vertex.words;
}
if (vertex.edges[word.charAt(0) - 97] == null) {
return 0;
}
return countWords(vertex.edges[word.charAt(0) - 97], word.substring(1));
}
int countPrefixes(Vertex vertex, String prefix) {
if (prefix.isEmpty()) {
return vertex.prefixes;
}
if (vertex.edges[prefix.charAt(0) - 97] == null) {
return 0;
}
return countPrefixes(vertex.edges[prefix.charAt(0) - 97], prefix.substring(1));
}
}
class Vertex {
int words;
int prefixes;
Vertex[] edges;
Vertex() {
words = 0;
prefixes = 0;
edges = new Vertex[26];
Arrays.fill(edges, null);
}
}
использованная литература
