【数据结构】子串、前缀

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)); // 初始化所有字符位置为 -1

    for (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);