后缀数组 - 元素码农

发布时间: 2025-03-21 19:56

↑

# 后缀数组

后缀数组（Suffix Array）是一种重要的字符串数据结构，它将给定字符串的所有后缀按字典序排序后得到的数组。这种数据结构在字符串处理、模式匹配等领域有广泛应用。

## 基本概念

### 定义

- 后缀：字符串从某个位置开始到末尾的连续子串
- 后缀数组：将所有后缀按字典序排序后，记录它们在原串中的起始位置形成的数组
- 名次数组：与后缀数组互逆的数组，记录每个后缀在排序后的名次

### 示例

对于字符串 "banana"：
1. 所有后缀：
   - banana (位置0)
   - anana (位置1)
   - nana (位置2)
   - ana (位置3)
   - na (位置4)
   - a (位置5)

2. 按字典序排序后：
   - a (位置5)
   - ana (位置3)
   - anana (位置1)
   - banana (位置0)
   - na (位置4)
   - nana (位置2)

3. 后缀数组SA = [5,3,1,0,4,2]

## 构造算法

### 倍增算法

```go
// 后缀数组结构
type SuffixArray struct {
    s    string   // 原始字符串
    sa   []int    // 后缀数组
    rank []int    // 名次数组
    tmp  []int    // 临时数组
    n    int      // 字符串长度
}

// 构造后缀数组
func NewSuffixArray(s string) *SuffixArray {
    n := len(s)
    sa := &SuffixArray{
        s:    s,
        sa:   make([]int, n),
        rank: make([]int, n),
        tmp:  make([]int, n),
        n:    n,
    }
    sa.build()
    return sa
}

// 倍增算法构建后缀数组
func (sa *SuffixArray) build() {
    n := sa.n
    
    // 初始化rank为字符的ASCII值
    for i := 0; i < n; i++ {
        sa.rank[i] = int(sa.s[i])
        sa.sa[i] = i
    }
    
    // 倍增过程
    for k := 1; k <= n; k *= 2 {
        // 按第二关键字排序
        sort.Slice(sa.sa, func(i, j int) bool {
            if sa.rank[sa.sa[i]] != sa.rank[sa.sa[j]] {
                return sa.rank[sa.sa[i]] < sa.rank[sa.sa[j]]
            }
            ri := -1
            if sa.sa[i]+k < n {
                ri = sa.rank[sa.sa[i]+k]
            }
            rj := -1
            if sa.sa[j]+k < n {
                rj = sa.rank[sa.sa[j]+k]
            }
            return ri < rj
        })
        
        // 计算新的rank值
        copy(sa.tmp, sa.rank)
        p := 0
        sa.rank[sa.sa[0]] = p
        for i := 1; i < n; i++ {
            if sa.tmp[sa.sa[i]] != sa.tmp[sa.sa[i-1]] ||
               sa.getSecondKey(sa.sa[i], k) != sa.getSecondKey(sa.sa[i-1], k) {
                p++
            }
            sa.rank[sa.sa[i]] = p
        }
        
        if p == n-1 {
            break
        }
    }
}

// 获取第二关键字
func (sa *SuffixArray) getSecondKey(pos, k int) int {
    if pos+k < sa.n {
        return sa.rank[pos+k]
    }
    return -1
}
```

### DC3算法

DC3（Difference Cover Modulo 3）算法是一种线性时间复杂度的后缀数组构造算法，适用于大规模字符串处理。其基本思想是：

1. 将后缀分为三类（mod 3）
2. 递归解决其中两类后缀的排序
3. 利用已排序的后缀推导剩余后缀的顺序

## 应用场景

### 字符串匹配

```go
// 在文本中查找模式串的所有出现位置
func (sa *SuffixArray) FindPattern(pattern string) []int {
    n, m := sa.n, len(pattern)
    result := make([]int, 0)
    
    // 二分查找上下界
    left := 0
    right := n - 1
    
    // 查找下界
    for left < right {
        mid := (left + right) / 2
        suffix := sa.s[sa.sa[mid]:]
        if strings.Compare(suffix[:min(len(suffix), m)], pattern) < 0 {
            left = mid + 1
        } else {
            right = mid
        }
    }
    
    start := left
    right = n - 1
    
    // 查找上界
    for left < right {
        mid := (left + right + 1) / 2
        suffix := sa.s[sa.sa[mid]:]
        if strings.Compare(suffix[:min(len(suffix), m)], pattern) > 0 {
            right = mid - 1
        } else {
            left = mid
        }
    }
    
    // 收集所有匹配位置
    for i := start; i <= right; i++ {
        if strings.HasPrefix(sa.s[sa.sa[i]:], pattern) {
            result = append(result, sa.sa[i])
        }
    }
    
    return result
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
```

### 最长公共前缀

```go
// 计算任意两个后缀的最长公共前缀长度
func (sa *SuffixArray) LCP(i, j int) int {
    if i == j {
        return len(sa.s) - i
    }
    
    length := 0
    for i+length < sa.n && j+length < sa.n && 
        sa.s[i+length] == sa.s[j+length] {
        length++
    }
    return length
}
```

### 重复子串查找

```go
// 查找最长重复子串
func (sa *SuffixArray) LongestRepeatedSubstring() string {
    maxLen := 0
    pos := 0
    
    // 比较相邻后缀的最长公共前缀
    for i := 1; i < sa.n; i++ {
        lcp := sa.LCP(sa.sa[i-1], sa.sa[i])
        if lcp > maxLen {
            maxLen = lcp
            pos = sa.sa[i]
        }
    }
    
    return sa.s[pos:pos+maxLen]
}
```

## 性能分析

### 时间复杂度

1. 构造
   - 倍增算法：O(nlog n)
   - DC3算法：O(n)

2. 查询操作
   - 模式匹配：O(mlog n + occ)，其中m为模式串长度，occ为出现次数
   - 最长公共前缀：O(1)（需要额外预处理）
   - 重复子串查找：O(n)

### 空间复杂度

- 基本后缀数组：O(n)
- 带有辅助数组：O(n)

## 优化技巧

1. 内存优化
   - 使用整数数组代替字符串存储
   - 压缩存储rank数组
   - 复用临时数组

2. 查询优化
   - 构建LCP数组加速查询
   - 使用RMQ（区间最小值查询）优化LCP计算
   - 二分查找优化模式匹配

## 实践建议

1. 选择合适算法
   - 小规模数据：倍增算法简单易实现
   - 大规模数据：考虑使用DC3算法
   - 特殊应用：根据具体需求选择优化方案

2. 注意事项
   - 处理边界情况
   - 考虑内存限制
   - 优化查询效率

## 总结

1. 优点
   - 强大的字符串查询能力
   - 支持多种字符串操作
   - 实现相对简单

2. 缺点
   - 构造时间较长
   - 内存消耗较大
   - 不支持动态修改

3. 适用场景
   - 字符串检索
   - 重复子串分析
   - 序列比较