🧮 常用算法大全

def quicksort(arr):
    """快速排序 - Python实现"""
    if len(arr) <= 1:
        return arr
    
    # 选择基准（取中间元素）
    pivot = arr[len(arr) // 2]
    
    # 分区
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    # 递归排序
    return quicksort(left) + middle + quicksort(right)

# 使用示例
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quicksort(arr)
print(sorted_arr)  # [1, 1, 2, 3, 6, 8, 10]

# ========== 原地排序版本（节省空间） ==========
def quicksort_inplace(arr, low, high):
    """原地快速排序"""
    if low < high:
        # 分区操作
        pi = partition(arr, low, high)
        
        # 递归排序子数组
        quicksort_inplace(arr, low, pi - 1)
        quicksort_inplace(arr, pi + 1, high)

def partition(arr, low, high):
    """分区函数"""
    pivot = arr[high]  # 选择最右边为基准
    i = low - 1
    
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# 使用
arr = [10, 7, 8, 9, 1, 5]
quicksort_inplace(arr, 0, len(arr) - 1)
print(arr)  # [1, 5, 7, 8, 9, 10]

package main

import "fmt"

func quickSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    
    pivot := arr[len(arr)/2]
    var left, middle, right []int
    
    for _, v := range arr {
        switch {
        case v < pivot:
            left = append(left, v)
        case v == pivot:
            middle = append(middle, v)
        case v > pivot:
            right = append(right, v)
        }
    }
    
    left = quickSort(left)
    right = quickSort(right)
    
    return append(append(left, middle...), right...)
}

// 原地排序版本
func quickSortInPlace(arr []int, low, high int) {
    if low < high {
        pi := partition(arr, low, high)
        quickSortInPlace(arr, low, pi-1)
        quickSortInPlace(arr, pi+1, high)
    }
}

func partition(arr []int, low, high int) int {
    pivot := arr[high]
    i := low - 1
    
    for j := low; j < high; j++ {
        if arr[j] <= pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1
}

func main() {
    arr := []int{3, 6, 8, 10, 1, 2, 1}
    sorted := quickSort(arr)
    fmt.Println(sorted) // [1 1 2 3 6 8 10]
}

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }
    
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                // 交换
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        
        // 将基准放到正确位置
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        
        return i + 1;
    }
    
    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr, 0, arr.length - 1);
        
        // 打印结果
        for (int num : arr) {
            System.out.print(num + " ");
        }
        // 输出: 1 5 7 8 9 10
    }
}

#include <iostream>
#include <vector>
using namespace std;

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    vector<int> arr = {10, 7, 8, 9, 1, 5};
    quickSort(arr, 0, arr.size() - 1);
    
    for (int num : arr) {
        cout << num << " ";
    }
    // 输出: 1 5 7 8 9 10
    
    return 0;
}

def binary_search(arr, target):
    """二分搜索 - 迭代实现"""
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # 避免溢出
        
        if arr[mid] == target:
            return mid  # 找到目标
        elif arr[mid] < target:
            left = mid + 1  # 在右半部分查找
        else:
            right = mid - 1  # 在左半部分查找
    
    return -1  # 未找到

# 递归实现
def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    
    mid = left + (right - left) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

# 使用
arr = [1, 3, 5, 7, 9, 11, 13, 15]
index = binary_search(arr, 7)
print(f"找到位置: {index}")  # 3

# ========== 二分搜索变种：查找边界 ==========
def search_left_bound(arr, target):
    """查找目标的最左边界"""
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return left

def search_right_bound(arr, target):
    """查找目标的最右边界"""
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    
    return left - 1

# 应用：查找区间
arr = [1, 2, 2, 2, 3, 4]
left = search_left_bound(arr, 2)
right = search_right_bound(arr, 2)
print(f"2出现在索引{left}到{right}")  # 1到3

package main

import "fmt"

func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    
    for left <= right {
        mid := left + (right-left)/2
        
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return -1
}

// 递归实现
func binarySearchRecursive(arr []int, target, left, right int) int {
    if left > right {
        return -1
    }
    
    mid := left + (right-left)/2
    
    if arr[mid] == target {
        return mid
    } else if arr[mid] < target {
        return binarySearchRecursive(arr, target, mid+1, right)
    } else {
        return binarySearchRecursive(arr, target, left, mid-1)
    }
}

func main() {
    arr := []int{1, 3, 5, 7, 9, 11, 13, 15}
    index := binarySearch(arr, 7)
    fmt.Printf("找到位置: %d\n", index)
}

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1;
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};
        int index = binarySearch(arr, 7);
        System.out.println("找到位置: " + index);
    }
}

#include <iostream>
#include <vector>
#include <algorithm>  // for std::binary_search
using namespace std;

int binarySearch(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
    
    // 自定义实现
    int index = binarySearch(arr, 7);
    cout << "找到位置: " << index << endl;
    
    // STL实现
    bool found = binary_search(arr.begin(), arr.end(), 7);
    cout << "是否找到: " << (found ? "是" : "否") << endl;
    
    // lower_bound和upper_bound
    auto lower = lower_bound(arr.begin(), arr.end(), 7);
    auto upper = upper_bound(arr.begin(), arr.end(), 7);
    cout << "位置: " << (lower - arr.begin()) << endl;
    
    return 0;
}

# ========== DFS递归实现 ==========
def dfs_recursive(graph, node, visited=None):
    """DFS递归实现"""
    if visited is None:
        visited = set()
    
    visited.add(node)
    print(node, end=' ')
    
    # 访问所有未访问的邻居
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
    return visited

# ========== DFS迭代实现（使用栈） ==========
def dfs_iterative(graph, start):
    """DFS迭代实现"""
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()  # 栈：后进先出
        
        if node not in visited:
            visited.add(node)
            print(node, end=' ')
            
            # 将未访问的邻居压入栈
            for neighbor in reversed(graph[node]):  # 反转保证顺序
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return visited

# ========== BFS广度优先搜索（使用队列） ==========
from collections import deque

def bfs(graph, start):
    """BFS实现"""
    visited = set([start])
    queue = deque([start])
    
    while queue:
        node = queue.popleft()  # 队列：先进先出
        print(node, end=' ')
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return visited

# 使用示例
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print("DFS递归:", end=' ')
dfs_recursive(graph, 'A')  # A B D E F C

print("\nDFS迭代:", end=' ')
dfs_iterative(graph, 'A')  # A B D E F C

print("\nBFS:", end=' ')
bfs(graph, 'A')  # A B C D E F (层次遍历)

package main

import "fmt"

type Graph map[string][]string

// DFS递归实现
func DFSRecursive(graph Graph, node string, visited map[string]bool) {
    visited[node] = true
    fmt.Print(node, " ")
    
    for _, neighbor := range graph[node] {
        if !visited[neighbor] {
            DFSRecursive(graph, neighbor, visited)
        }
    }
}

// BFS实现
func BFS(graph Graph, start string) {
    visited := make(map[string]bool)
    queue := []string{start}
    visited[start] = true
    
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]  // 出队
        fmt.Print(node, " ")
        
        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor)
            }
        }
    }
}

func main() {
    graph := Graph{
        "A": {"B", "C"},
        "B": {"A", "D", "E"},
        "C": {"A", "F"},
        "D": {"B"},
        "E": {"B", "F"},
        "F": {"C", "E"},
    }
    
    fmt.Print("DFS: ")
    DFSRecursive(graph, "A", make(map[string]bool))
    
    fmt.Print("\nBFS: ")
    BFS(graph, "A")
}

# ========== 示例1：斐波那契数列 ==========
# 暴力递归（指数级时间，很慢）
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n-1) + fib_naive(n-2)

# DP优化（线性时间）
def fib_dp(n):
    if n <= 1:
        return n
    
    dp = [0] * (n + 1)
    dp[1] = 1
    
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

# 空间优化（只需两个变量）
def fib_optimized(n):
    if n <= 1:
        return n
    
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    
    return curr

print(fib_dp(10))  # 55

# ========== 示例2：0-1背包问题 ==========
def knapsack(weights, values, capacity):
    """
    0-1背包：每个物品只能选一次
    weights: 物品重量列表
    values: 物品价值列表
    capacity: 背包容量
    """
    n = len(weights)
    
    # dp[i][w]表示前i个物品，容量为w时的最大价值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            # 不选第i个物品
            dp[i][w] = dp[i-1][w]
            
            # 选第i个物品（如果放得下）
            if weights[i-1] <= w:
                dp[i][w] = max(
                    dp[i][w],
                    dp[i-1][w - weights[i-1]] + values[i-1]
                )
    
    return dp[n][capacity]

# 使用
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
max_value = knapsack(weights, values, capacity)
print(f"最大价值: {max_value}")  # 10

# ========== 示例3：最长公共子序列（LCS） ==========
def longest_common_subsequence(text1, text2):
    """最长公共子序列"""
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]

lcs_len = longest_common_subsequence("abcde", "ace")
print(f"LCS长度: {lcs_len}")  # 3 (ace)

package main

import "fmt"

// 0-1背包问题
func knapsack(weights, values []int, capacity int) int {
    n := len(weights)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, capacity+1)
    }
    
    for i := 1; i <= n; i++ {
        for w := 1; w <= capacity; w++ {
            dp[i][w] = dp[i-1][w]
            
            if weights[i-1] <= w {
                dp[i][w] = max(
                    dp[i][w],
                    dp[i-1][w-weights[i-1]] + values[i-1],
                )
            }
        }
    }
    
    return dp[n][capacity]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    weights := []int{2, 3, 4, 5}
    values := []int{3, 4, 5, 6}
    capacity := 8
    
    maxValue := knapsack(weights, values, capacity)
    fmt.Printf("最大价值: %d\n", maxValue)
}

# ========== 示例1：N皇后问题 ==========
def solve_n_queens(n):
    """N皇后问题"""
    result = []
    board = [['.'] * n for _ in range(n)]
    
    def is_valid(row, col):
        # 检查列
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        
        # 检查左上对角线
        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if board[i][j] == 'Q':
                return False
            i, j = i - 1, j - 1
        
        # 检查右上对角线
        i, j = row - 1, col + 1
        while i >= 0 and j < n:
            if board[i][j] == 'Q':
                return False
            i, j = i - 1, j + 1
        
        return True
    
    def backtrack(row):
        if row == n:
            # 找到一个解
            result.append([''.join(row) for row in board])
            return
        
        for col in range(n):
            if is_valid(row, col):
                board[row][col] = 'Q'  # 做选择
                backtrack(row + 1)     # 进入下一层
                board[row][col] = '.'  # 撤销选择（回溯）
    
    backtrack(0)
    return result

# 使用
solutions = solve_n_queens(4)
print(f"4皇后有{len(solutions)}个解")

# ========== 示例2：全排列 ==========
def permute(nums):
    """生成数组的所有排列"""
    result = []
    
    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return
        
        for i in range(len(remaining)):
            path.append(remaining[i])
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()  # 回溯
    
    backtrack([], nums)
    return result

perms = permute([1, 2, 3])
print(f"全排列数量: {len(perms)}")  # 6

# ========== 示例3：子集生成 ==========
def subsets(nums):
    """生成所有子集"""
    result = []
    
    def backtrack(start, path):
        result.append(path[:])
        
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    
    backtrack(0, [])
    return result

all_subsets = subsets([1, 2, 3])
print(f"子集数量: {len(all_subsets)}")  # 8

# ========== 无重复字符的最长子串 ==========
def length_of_longest_substring(s):
    """
    LeetCode 3: 无重复字符的最长子串
    输入: "abcabcbb"
    输出: 3 ("abc")
    """
    char_set = set()
    left = 0
    max_len = 0
    
    for right in range(len(s)):
        # 如果有重复，移动左指针
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
    
    return max_len

print(length_of_longest_substring("abcabcbb"))  # 3

# ========== 最小覆盖子串 ==========
from collections import Counter

def min_window(s, t):
    """
    LeetCode 76: 最小覆盖子串
    输入: s = "ADOBECODEBANC", t = "ABC"
    输出: "BANC"
    """
    if not s or not t:
        return ""
    
    need = Counter(t)
    window = {}
    left = right = 0
    valid = 0  # 窗口中满足need条件的字符个数
    
    # 记录最小子串的起始位置和长度
    start = 0
    min_len = float('inf')
    
    while right < len(s):
        # 扩大窗口
        c = s[right]
        right += 1
        
        if c in need:
            window[c] = window.get(c, 0) + 1
            if window[c] == need[c]:
                valid += 1
        
        # 收缩窗口
        while valid == len(need):
            # 更新最小子串
            if right - left < min_len:
                start = left
                min_len = right - left
            
            d = s[left]
            left += 1
            
            if d in need:
                if window[d] == need[d]:
                    valid -= 1
                window[d] -= 1
    
    return "" if min_len == float('inf') else s[start:start + min_len]

print(min_window("ADOBECODEBANC", "ABC"))  # "BANC"

# ========== 两数之和（有序数组） ==========
def two_sum_sorted(numbers, target):
    """
    输入: numbers = [2,7,11,15], target = 9
    输出: [0, 1]  # numbers[0] + numbers[1] = 9
    """
    left, right = 0, len(numbers) - 1
    
    while left < right:
        current_sum = numbers[left] + numbers[right]
        
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1  # 和太小，左指针右移
        else:
            right -= 1  # 和太大，右指针左移
    
    return []

# ========== 三数之和 ==========
def three_sum(nums):
    """
    找出所有和为0的三元组
    输入: [-1,0,1,2,-1,-4]
    输出: [[-1,-1,2],[-1,0,1]]
    """
    nums.sort()  # 先排序
    result = []
    
    for i in range(len(nums) - 2):
        # 跳过重复元素
        if i > 0 and nums[i] == nums[i-1]:
            continue
        
        # 转化为两数之和
        left, right = i + 1, len(nums) - 1
        target = -nums[i]
        
        while left < right:
            current_sum = nums[left] + nums[right]
            
            if current_sum == target:
                result.append([nums[i], nums[left], nums[right]])
                
                # 跳过重复
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                
                left += 1
                right -= 1
            elif current_sum < target:
                left += 1
            else:
                right -= 1
    
    return result

# ========== 盛最多水的容器 ==========
def max_area(height):
    """
    双指针贪心：每次移动高度较小的那一边
    """
    left, right = 0, len(height) - 1
    max_water = 0
    
    while left < right:
        width = right - left
        area = min(height[left], height[right]) * width
        max_water = max(max_water, area)
        
        # 移动高度较小的指针
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_water

class UnionFind:
    """并查集（带路径压缩和按秩合并）"""
    
    def __init__(self, n):
        self.parent = list(range(n))  # 每个节点的父节点
        self.rank = [0] * n           # 树的高度
        self.count = n                # 连通分量数量
    
    def find(self, x):
        """查找根节点（带路径压缩）"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]
    
    def union(self, x, y):
        """合并两个集合（按秩合并）"""
        root_x = self.find(x)
        root_y = self.find(y)
        
        if root_x == root_y:
            return False  # 已在同一集合
        
        # 按秩合并：将矮树连到高树
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        
        self.count -= 1
        return True
    
    def connected(self, x, y):
        """判断是否连通"""
        return self.find(x) == self.find(y)

# ========== 应用：朋友圈数量 ==========
def find_circle_num(is_connected):
    """
    LeetCode 547: 省份数量
    """
    n = len(is_connected)
    uf = UnionFind(n)
    
    for i in range(n):
        for j in range(i + 1, n):
            if is_connected[i][j] == 1:
                uf.union(i, j)
    
    return uf.count

# 使用
matrix = [
    [1, 1, 0],
    [1, 1, 0],
    [0, 0, 1]
]
print(f"朋友圈数量: {find_circle_num(matrix)}")  # 2

package main

import "fmt"

type UnionFind struct {
    parent []int
    rank   []int
    count  int
}

func NewUnionFind(n int) *UnionFind {
    uf := &UnionFind{
        parent: make([]int, n),
        rank:   make([]int, n),
        count:  n,
    }
    for i := range uf.parent {
        uf.parent[i] = i
    }
    return uf
}

func (uf *UnionFind) Find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.Find(uf.parent[x])  // 路径压缩
    }
    return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) bool {
    rootX, rootY := uf.Find(x), uf.Find(y)
    
    if rootX == rootY {
        return false
    }
    
    // 按秩合并
    if uf.rank[rootX] < uf.rank[rootY] {
        uf.parent[rootX] = rootY
    } else if uf.rank[rootX] > uf.rank[rootY] {
        uf.parent[rootY] = rootX
    } else {
        uf.parent[rootY] = rootX
        uf.rank[rootX]++
    }
    
    uf.count--
    return true
}

func main() {
    uf := NewUnionFind(10)
    uf.Union(0, 1)
    uf.Union(1, 2)
    fmt.Printf("连通分量数: %d\n", uf.count)
}

# ========== 区间调度问题 ==========
def interval_schedule(intervals):
    """
    给定多个活动，每次只能参加一个，求最多能参加几个
    输入: [[1,3], [2,4], [3,5]]
    输出: 2
    """
    if not intervals:
        return 0
    
    # 按结束时间排序（贪心策略）
    intervals.sort(key=lambda x: x[1])
    
    count = 1
    end = intervals[0][1]
    
    for i in range(1, len(intervals)):
        # 如果当前活动开始时间>=上个活动结束时间
        if intervals[i][0] >= end:
            count += 1
            end = intervals[i][1]
    
    return count

# ========== 跳跃游戏II（最少跳跃次数） ==========
def jump(nums):
    """
    每次跳最远能跳到的位置
    """
    n = len(nums)
    jumps = 0
    current_end = 0
    farthest = 0
    
    for i in range(n - 1):
        farthest = max(farthest, i + nums[i])
        
        # 到达当前跳跃的边界
        if i == current_end:
            jumps += 1
            current_end = farthest
    
    return jumps

print(jump([2,3,1,1,4]))  # 2 (跳1步到索引1,再跳1步到末尾)

def kmp_search(text, pattern):
    """
    KMP字符串匹配算法
    时间复杂度：O(m + n)
    """
    def build_lps(pattern):
        """构建最长公共前后缀数组（LPS）"""
        lps = [0] * len(pattern)
        length = 0
        i = 1
        
        while i < len(pattern):
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        
        return lps
    
    if not pattern:
        return 0
    
    lps = build_lps(pattern)
    i = j = 0  # i指向text，j指向pattern
    
    while i < len(text):
        if text[i] == pattern[j]:
            i += 1
            j += 1
        
        if j == len(pattern):
            return i - j  # 找到匹配
        elif i < len(text) and text[i] != pattern[j]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    
    return -1  # 未找到

# 使用
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
index = kmp_search(text, pattern)
print(f"匹配位置: {index}")  # 10

package main

import "fmt"

func buildLPS(pattern string) []int {
    lps := make([]int, len(pattern))
    length := 0
    i := 1
    
    for i < len(pattern) {
        if pattern[i] == pattern[length] {
            length++
            lps[i] = length
            i++
        } else {
            if length != 0 {
                length = lps[length-1]
            } else {
                lps[i] = 0
                i++
            }
        }
    }
    
    return lps
}

func kmpSearch(text, pattern string) int {
    if len(pattern) == 0 {
        return 0
    }
    
    lps := buildLPS(pattern)
    i, j := 0, 0
    
    for i < len(text) {
        if text[i] == pattern[j] {
            i++
            j++
        }
        
        if j == len(pattern) {
            return i - j
        } else if i < len(text) && text[i] != pattern[j] {
            if j != 0 {
                j = lps[j-1]
            } else {
                i++
            }
        }
    }
    
    return -1
}

func main() {
    text := "ABABDABACDABABCABAB"
    pattern := "ABABCABAB"
    index := kmpSearch(text, pattern)
    fmt.Printf("匹配位置: %d\n", index)
}