Cấu trúc dữ liệu và Giải thuật Bài 117: Máy tự động hậu tố (Suffix Automaton - SAM) - Cấu trúc dữ liệu chuỗi tối thượng với kích thước tuyến tính.

Trong lý thuyết xử lý chuỗi nâng cao, Suffix Tree biểu diễn toàn bộ hậu tố nhưng việc cài đặt thuật toán tuyến tính Ukkonen đòi hỏi xử lý nhiều trường hợp biên phức tạp; trong khi đó, Suffix Array cần đi kèm mảng LCP và cấu trúc RMQ để truy vấn hiệu quả. Máy tự động hậu tố (Suffix Automaton - SAM) giải quyết bài toán này bằng cách nén toàn bộ thông tin của mọi chuỗi con trong một xâu ký tự vào một đồ thị có hướng không chu trình (DAG) với số lượng trạng thái tối đa $2N - 1$ và số cung chuyển trạng thái tối đa $3N - 4$ , cho phép xây dựng trực tuyến (online) chỉ trong thời gian $O(N)$ .

1. Bản chất toán học và Lớp tương đương $\text{endpos}$

Cho chuỗi $S$ có độ dài $N$ . Với mỗi chuỗi con $u$ xuất hiện trong $S$ , tập $\text{endpos}(u)$ được định nghĩa là tập hợp các chỉ số kết thúc của các lần xuất hiện của $u$ trong $S$ :

$\text{endpos}(u) = \{ i \mid S[i - \vert{}u\vert{} + 1 \dots i] = u \}$

Ví dụ với chuỗi $S = \text{"abacaba"}$ :

$\text{endpos}(\text{"a"}) = \{0, 2, 4, 6\}$
$\text{endpos}(\text{"aba"}) = \{2, 6\}$
$\text{endpos}(\text{"caba"}) = \{6\}$

Các định lý then chốt của $\text{endpos}$

Tính lồng nhau hoặc rời rạc: Với hai chuỗi con bất kỳ $u$ và $v$ ( $\vert{}u\vert{} \le \vert{}v\vert{}$ ), hai tập $\text{endpos}(u)$ và $\text{endpos}(v)$ hoặc hoàn toàn không giao nhau, hoặc $\text{endpos}(v) \subseteq \text{endpos}(u)$ . Tập hợp con xảy ra khi và chỉ khi $u$ là một hậu tố của $v$ .
Lớp tương đương (Equivalence Class): Các chuỗi con có tập $\text{endpos}$ giống hệt nhau được gom vào cùng một trạng thái trong SAM.
Cấu trúc chuỗi trong một trạng thái: Tất cả chuỗi con thuộc cùng một trạng thái đều là hậu tố của nhau, với độ dài liên tục nằm trong đoạn $[\text{minlen}(u), \text{len}(u)]$ , trong đó $\text{len}(u)$ là độ dài của chuỗi con dài nhất trong trạng thái đó.

2. Cấu trúc Suffix Link và Cây liên kết

Do các tập hợp $\text{endpos}$ có tính chất lồng nhau, chúng hình thành một cấu trúc cây phân cấp:

Suffix Link (link): Với trạng thái $u$ , $\text{link}(u)$ trỏ tới trạng thái $v$ có $\text{endpos}(v)$ là tập mẹ nhỏ nhất chứa $\text{endpos}(u)$ .
Về mặt ký tự, trạng thái $\text{link}(u)$ chứa hậu tố dài nhất của các chuỗi trong $u$ mà bắt đầu xuất hiện ở những vị trí khác ngoài các vị trí trong $\text{endpos}(u)$ .
Mối quan hệ độ dài: $\text{minlen}(u) = \text{len}(\text{link}(u)) + 1$ .
Toàn bộ các cung link hướng về gốc tạo thành một cây gọi là Link Tree (cây này đẳng cấu với Suffix Tree của chuỗi $S$ đảo ngược).

3. Thuật toán xây dựng Online trong $O(N)$

Thuật toán bổ sung từng ký tự $c$ vào cuối chuỗi hiện tại và cập nhật SAM theo các bước:

Tạo trạng thái mới cur với $\text{len}(\text{cur}) = \text{len}(\text{last}) + 1$ .
Duyệt ngược từ last theo các con trỏ link:
- Nếu trạng thái $p$ chưa có chuyển trạng thái theo $c$ , gán next[p][c] = cur.
- Lặp lại cho đến khi gặp trạng thái $p$ đã có chuyển trạng thái theo $c$ , hoặc chạm tới gốc ( $-1$ ).
Nếu không có trạng thái nào có chuyển tiếp theo $c$ , gán link(cur) = root.
Nếu tìm thấy $p$ có chuyển tiếp theo $c$ tới trạng thái $q$ :
- Trường hợp tối ưu ( $\text{len}(q) == \text{len}(p) + 1$ ): Chuỗi dài nhất qua $q$ chỉ đơn giản là nối thêm $c$ vào chuỗi dài nhất của $p$ . Ta chỉ cần gán link(cur) = q.
- Trường hợp phân tách (Split / Clone): $\text{len}(q) > \text{len}(p) + 1$ . Trạng thái $q$ đang chứa cả các chuỗi con khác không đi qua $p$ . Ta nhân bản (clone) trạng thái $q$ thành một trạng thái mới clone với $\text{len}(\text{clone}) = \text{len}(p) + 1$ , sao chép toàn bộ chuyển tiếp của $q$ sang clone, gán link(clone) = link(q), sau đó trỏ link(q) = clone và link(cur) = clone. Cuối cùng, duyệt ngược từ $p$ theo link để chuyển hướng các cung đang trỏ vào $q$ sang clone.
Cập nhật last = cur.

4. Hiện thực hóa Suffix Automaton bằng Golang

Đoạn code dưới đây cài đặt cấu trúc SAM với đầy đủ thuật toán xây dựng trực tuyến, hàm đếm số lượng chuỗi con phân biệt và hàm kiểm tra sự tồn tại của mẫu trong chuỗi:

package main

import (
	"fmt"
)

type State struct {
	len  int
	link int
	next map[rune]int
}

type SuffixAutomaton struct {
	st   []State
	sz   int
	last int
}

func NewSuffixAutomaton(maxLen int) *SuffixAutomaton {
	// SAM có tối đa 2*N - 1 trạng thái
	sam := &SuffixAutomaton{
		st:   make([]State, 2*maxLen),
		sz:   1,
		last: 0,
	}
	sam.st[0].len = 0
	sam.st[0].link = -1
	sam.st[0].next = make(map[rune]int)
	return sam
}

// Thêm một ký tự c vào SAM: Amortized O(1)
func (sam *SuffixAutomaton) Extend(c rune) {
	cur := sam.sz
	sam.sz++
	sam.st[cur].len = sam.st[sam.last].len + 1
	sam.st[cur].next = make(map[rune]int)

	p := sam.last
	for p != -1 {
		if _, exists := sam.st[p].next[c]; exists {
			break
		}
		sam.st[p].next[c] = cur
		p = sam.st[p].link
	}

	if p == -1 {
		sam.st[cur].link = 0
	} else {
		q := sam.st[p].next[c]
		if sam.st[p].len+1 == sam.st[q].len {
			sam.st[cur].link = q
		} else {
			// Tách trạng thái q
			clone := sam.sz
			sam.sz++
			sam.st[clone].len = sam.st[p].len + 1
			sam.st[clone].next = make(map[rune]int)
			for k, v := range sam.st[q].next {
				sam.st[clone].next[k] = v
			}
			sam.st[clone].link = sam.st[q].link

			for p != -1 && sam.st[p].next[c] == q {
				sam.st[p].next[c] = clone
				p = sam.st[p].link
			}

			sam.st[q].link = clone
			sam.st[cur].link = clone
		}
	}

	sam.last = cur
}

// Xây dựng SAM từ một chuỗi văn bản
func BuildSAM(s string) *SuffixAutomaton {
	sam := NewSuffixAutomaton(len(s))
	for _, ch := range s {
		sam.Extend(ch)
	}
	return sam
}

// Đếm tổng số lượng chuỗi con phân biệt: O(V)
func (sam *SuffixAutomaton) CountDistinctSubstrings() int64 {
	var total int64 = 0
	for i := 1; i < sam.sz; i++ {
		total += int64(sam.st[i].len - sam.st[sam.st[i].link].len)
	}
	return total
}

// Kiểm tra xem mẫu pattern có phải là chuỗi con không: O(|pattern|)
func (sam *SuffixAutomaton) Contains(pattern string) bool {
	curr := 0
	for _, ch := range pattern {
		nextState, exists := sam.st[curr].next[ch]
		if !exists {
			return false
		}
		curr = nextState
	}
	return true
}

func main() {
	text := "abacaba"
	sam := BuildSAM(text)

	fmt.Printf("Chuỗi gốc: \"%s\"\n", text)
	fmt.Printf("Số trạng thái được tạo: %d\n", sam.sz)
	fmt.Printf("Tổng số chuỗi con phân biệt: %d\n", sam.CountDistinctSubstrings())

	// Kiểm tra truy vấn chuỗi con
	queries := []string{"aba", "caba", "bac", "xyz", "abacaba"}
	for _, q := range queries {
		fmt.Printf("Chứa \"%s\"? -> %t\n", q, sam.Contains(q))
	}
}

5. Các ứng dụng thực tế của Suffix Automaton

Tính số chuỗi con phân biệt: Mỗi trạng thái $u$ đóng góp đúng $\text{len}(u) - \text{len}(\text{link}(u))$ chuỗi con độc nhất. Tính tổng toàn bộ các trạng thái chỉ mất một vòng lặp qua mảng trạng thái $O(N)$ .
Tìm chuỗi con chung dài nhất của hai chuỗi (LCS): Dựng SAM cho chuỗi $S$ . Duyệt chuỗi $T$ trên SAM, duy trì biến độ dài khớp lớn nhất tương tự như cách di chuyển trên máy tự động. Thuật toán chạy trong $O(\vert{}S\vert{} + \vert{}T\vert{})$ mà không cần cấu trúc phân cấp nặng nề.
Tìm chuỗi con xuất hiện lần đầu sớm nhất: Lưu thêm trường first_pos cho mỗi trạng thái khi khởi tạo và lan truyền qua phép nhân bản để giải quyết truy vấn trong $O(M)$ .

cấu trúc dữ liệu

1. Bản chất toán học và Lớp tương đương endpos\text{endpos}endpos

Các định lý then chốt của endpos\text{endpos}endpos