目录
二分搜索（适用于有序字符串数组）
基本概念 二分搜索（Binary Search）是一种高效的查找算法，适用于在有序数组中查找特定元素。与线性搜索相比，二分搜索通过逐步减少搜索范围，大幅提高查找效率。
算法步骤
- 确定中间元素：首先计算数组的中间索引
mid，并获取该索引处的元素mid_val。 - 比较目标字符串：
-
- 如果目标字符串等于
mid_val，则查找成功，返回该索引。 - 如果目标字符串小于
mid_val，则在数组的左半部分继续搜索。 - 如果目标字符串大于
mid_val，则在数组的右半部分继续搜索。
- 如果目标字符串等于
- 递归或迭代：根据以上步骤不断递归地搜索左半部分或右半部分，直到找到目标字符串或搜索区间缩小到空区间（未找到）。
代码示例
python语言：
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:p
mid = left + (right - left) // 2 # 避免溢出
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # 未找到
# 示例使用
arr = ["apple", "banana", "cherry", "date", "fig", "grape"]
target = "date"
result = binary_search(arr, target)
if result != -1:
print(f"字符串'{target}'在索引 {result} 处找到。")
else:
print(f"字符串'{target}'未找到。")C语言：
#include <stdio.h>
#include <string.h>
// 二分查找函数
int binarySearch(char *arr[], char *target, int left, int right) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (strcmp(arr[mid], target) == 0) {
return mid;
} else if (strcmp(arr[mid], target) < 0) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
// 测试示例
int main() {
char *arr[] = {"apple", "banana", "cherry", "date", "fig", "grape"};
char *target = "date";
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, target, 0, n - 1);
if (result!= -1) {
printf("字符串'%s'在索引 %d 处找到。\n", target, result);
} else {
printf("字符串'%s'未找到。\n", target);
}
return 0;
}输出结果
字符串'date'在索引 3 处找到。复杂度分析
- 时间复杂度：二分搜索的时间复杂度为O(log n)，因为每次搜索都将查找范围缩小一半。
- 空间复杂度：二分搜索的空间复杂度为O(1)，不需要额外的存储空间。
应用场景 二分搜索主要用于在有序数组中查找元素，是高效的查找算法，广泛应用于查找问题中，例如数据库查询、词典查找等。
Trie树（前缀树）
结构定义 Trie树，又称前缀树或字典树，是一种树形数据结构，主要用于快速存储和查找字符串的前缀。Trie树中的每个节点代表一个字符，根节点为空，路径上的字符连接表示一个字符串。
插入与搜索操作
- 插入操作：依次将字符串中的字符插入Trie树中，如果字符路径不存在，则创建新节点。如果路径存在，则继续沿着路径插入。
- 搜索操作：从根节点开始，依次沿着字符路径遍历Trie树。如果能到达字符串的末尾节点且该节点标记为终止，则说明字符串存在。
代码示例
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
# 示例使用
trie = Trie()
words = ["hello", "world", "hell", "word"]
for word in words:
trie.insert(word)
print(trie.search("hell")) # 输出: True
print(trie.search("hello")) # 输出: True
print(trie.search("word")) # 输出: True
print(trie.search("wor")) # 输出: FalseC语言：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ALPHABET_SIZE 26
// Trie 节点结构体
typedef struct TrieNode {
struct TrieNode *children[ALPHABET_SIZE];
int is_end_of_word;
} TrieNode;
// 创建新的 Trie 节点
TrieNode *createNode() {
TrieNode *newNode = (TrieNode *)malloc(sizeof(TrieNode));
if (newNode) {
newNode->is_end_of_word = 0;
for (int i = 0; i < ALPHABET_SIZE; i++) {
newNode->children[i] = NULL;
}
}
return newNode;
}
// 插入单词到 Trie
void insert(TrieNode *root, char *word) {
TrieNode *node = root;
int len = strlen(word);
for (int i = 0; i < len; i++) {
int index = word[i] - 'a';
if (!node->children[index]) {
node->children[index] = createNode();
}
node = node->children[index];
}
node->is_end_of_word = 1;
}
// 搜索单词是否在 Trie 中
int search(TrieNode *root, char *word) {
TrieNode *node = root;
int len = strlen(word);
for (int i = 0; i < len; i++) {
int index = word[i] - 'a';
if (!node->children[index]) {
return 0;
}
node = node->children[index];
}
return node->is_end_of_word;
}
int main() {
TrieNode *root = createNode();
char *words[] = {"hello", "world", "hell", "word"};
int numWords = sizeof(words) / sizeof(words[0]);
for (int i = 0; i < numWords; i++) {
insert(root, words[i]);
}
printf("%d\n", search(root, "hell"));
printf("%d\n", search(root, "hello"));
printf("%d\n", search(root, "word"));
printf("%d\n", search(root, "wor"));
return 0;
}应用场景
- 自动补全：在输入搜索词时，根据已输入的前缀快速查找可能的完整词语。
- 拼写检查：检查输入单词是否存在于词典中，或建议正确拼写。
- 词频统计：统计以特定前缀开头的单词出现频率。
推荐视频：
推荐题目：
后缀树与后缀数组
基本概念
- 后缀树（Suffix Tree）：后缀树是一种基于树的数据结构，用于存储一个字符串的所有后缀。它通过记录从字符串某个位置开始的所有子串，能够快速解决许多字符串处理问题。
- 后缀数组（Suffix Array）：后缀数组是一个数组，其中每个元素记录了一个后缀在原字符串中的起始位置。后缀数组是后缀树的线性空间优化形式，适合在内存紧张的环境中使用。
构造方法
- 后缀树的构造：通过逐步插入字符串的所有后缀来构造后缀树，每个后缀插入时从根节点开始，沿着现有路径插入字符，直到匹配完所有字符或找到一个分支点。
- 后缀数组的构造：对字符串的所有后缀进行排序，并记录每个后缀在原字符串中的起始位置，从而形成后缀数组。
代码示例
python语言：
def build_suffix_array(s):
n = len(s)
suffixes = [(s[i:], i) for i in range(n)]
suffixes.sort()
suffix_array = [suffix[1] for suffix in suffixes]
return suffix_array
# 示例使用
s = "banana"
suffix_array = build_suffix_array(s)
print(suffix_array) # 输出: [5, 3, 1, 0, 4, 2]C语言：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 比较两个后缀字符串的函数
int compareSuffix(const void *a, const void *b) {
const char *suffix1 = ((const struct Suffix *)a)->suffix;
const char *suffix2 = ((const struct Suffix *)b)->suffix;
return strcmp(suffix1, suffix2);
}
// 后缀结构体
typedef struct Suffix {
char *suffix;
int index;
} Suffix;
// 构建后缀数组的函数
int *buildSuffixArray(const char *s) {
int n = strlen(s);
Suffix *suffixes = (Suffix *)malloc(n * sizeof(Suffix));
for (int i = 0; i < n; i++) {
suffixes[i].suffix = strdup(s + i);
suffixes[i].index = i;
}
qsort(suffixes, n, sizeof(Suffix), compareSuffix);
int *suffixArray = (int *)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
suffixArray[i] = suffixes[i].index;
}
// 释放内存
for (int i = 0; i < n n; i++) {
free(suffixes[i].suffix);
}
free(suffixes);
return suffixArray;
}
// 测试示例
int main() {
const char *s = "banana";
int *suffixArray = buildSuffixArray(s);
for (int i = 0; i < strlen(s); i++) {
printf("%d ", suffixArray[i]);
}
printf("\n");
free(suffixArray);
return 0;
}应用场景
- 最长公共子串：通过比较两个字符串的后缀树或后缀数组，找到最长公共子串。
- 字符串排序：对字符串的所有后缀进行排序，可用于解决如词典序问题。
- 重复子串查找：在一个字符串中快速查找所有的重复子串。