【数据结构】子串、前缀

1. 子串 (Substring)

   • 字符串中连续的一段字符序列，例如 "abc" 是 "abcd" 的子串。

   • 特点：必须连续，顺序不可改变。

2. 子序列 (Subsequence)

   • 字符串中不连续但保持顺序的字符序列，例如 "acd" 是 "abcd" 的子序列。

3. 前缀 (Prefix)

   • 字符串开头的子串，例如 "a", "ab", "abc" 都是 "abcde" 的前缀。

4. 后缀 (Suffix)

   • 字符串结尾的子串，例如 "e", "de", "cde" 是 "abcde" 的后缀。

KMP 前缀函数（计算 next 数组）

#include <stdlib.h>
#include <string.h>int* compute_prefix_function(const char* pattern) {int n = strlen(pattern);int* next = (int*)malloc(n * sizeof(int));if (next == NULL) return NULL;int j = 0;next[0] = 0;for (int i = 1; i < n; i++) {while (j > 0 && pattern[i] != pattern[j]) {j = next[j - 1];}if (pattern[i] == pattern[j]) {j++;}next[i] = j;}return next; // 调用者需自行 free 释放内存
}// 示例用法：
// const char* pattern = "ababaca";
// int* next = compute_prefix_function(pattern);
// free(next);

滑动窗口（最长无重复子串）

int longest_unique_substring(const char* s) {int max_len = 0;int left = 0;int char_map[256]; // 假设字符为 ASCII 码memset(char_map, -1, sizeof(char_map)); // 初始化所有字符位置为 -1for (int right = 0; s[right] != '\0'; right++) {char c = s[right];if (char_map[c] >= left) {left = char_map[c] + 1;}char_map[c] = right;int current_len = right - left + 1;if (current_len > max_len) {max_len = current_len;}}return max_len;
}// 示例用法：
// const char* s = "abcabcbb";
// int result = longest_unique_substring(s);