[数据结构与算法]《数据结构》：04串

串的定义

串，即字符串（String）是由零个或多个字符组成的有限序列。一般记为 S = 'a1a2······an'（n ≥0）

其中，S 是串名，单引号括起来的字符序列是串的值；ai 可以是字母、数字或其他字符；串中字符的个数 n 称为串的长度。n = 0 时的串称为空串（用?表示）。

例：S="HelloWorld!" T='iPhone 11 Pro Max?'

**子串：**串中任意个连续的字符组成的子序列。 Eg：’iPhone’，’Pro M’ 是串 T 的子串

**主串：**包含子串的串。 Eg：T 是子串 ’iPhone’ 的主串

**字符在主串中的位置：**字符在串中的序号。 Eg：’1’ 在T中的位置是 8（第一次出现）

**子串在主串中的位置：**子串的第一个字符在主串中的位置 。 Eg：’11 Pro’ 在 T 中的位置为 8

串的存储结构

定长顺序存储表示

类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值得字符序列。在串的定长顺序存储结构中，为每个串变量分配一个固定长度的存储区，即定长数组。

堆分配存储表示

堆分配存储表示仍然以一组地址连续的存储单元存放串值得字符序列，但它们得存储空间是在程序执行过程中动态分配得到得。

块链存储表示

类似于线性表得链式存储结构，也可采用链表方式存储串值。由于串得特殊性（每个元素只有一个字符），在具体实现时，每个结点即可以存放一个字符，也可以存放多个字符。每个结点称为块，整个链表称为块链结构。

串的基本操作

串的模式匹配

简单的模式匹配算法

子串的定位操作通常称为串的模式匹配，它求的是子串（常称模式串）在主串中的位置。这里采用定长顺序存储结构，给出一种不依赖于其他串操作的暴力匹配算法。

package main

import "fmt"

func Index(S string, T string) int {
	i, j := 0, 0
	for i < len(S) && j < len(T) {
		if S[i] == T[j] {
			i++
			j++
		} else {
			i = i - j + 1
			j = 0
		}
	}

	if j >= len(T) {
		return i - len(T) + 1
	} else {
		return 0
	}
}

func main() {
	a := "ababcabcacbab"
	b := "abcac"

	c := Index(a, b)
	fmt.Println(c) // 6
}

暴力模式匹配算法的最坏时间复杂度为 O(nm)，其中 n 和 m 分别为主串和模式串的长度。

KMP模式匹配算法

package main

import "fmt"

func GetNext(T string, next []int) {
	i, j := 1, 0
	next[1] = 0
	for i < len(T) {
		if j == 0 || T[i] == T[j] {
			i++
			j++
			next[i] = j
		} else {
			j = next[j]
		}
	}
}

func IndexKMP(S string, T string) int {
	i, j := 1, 1
	next := make([]int, len(T)+1)
	GetNext(T, next)
	for i < len(S) && j < len(T) {
		if j == 0 || S[i] == T[j] {
			i++
			j++
		} else {
			j = next[j]
		}
	}

	if j >= len(T) {
		return i - len(T) + 1
	} else {
		return 0
	}
}

func main() {
	a := "ababcabcacbab"
	b := "abcac"

	c := IndexKMP(a, b)
	fmt.Println(c) // 6
}

KMP算法的进一步优化

package main

import "fmt"

func GetNextVal(T string, nextVal []int) {
	i, j := 1, 0
	nextVal[1] = 0
	for i < len(T)-1 {
		if j == 0 || T[i] == T[j] {
			i++
			j++
			if T[i] == T[j] {
				nextVal[i] = nextVal[j]
			} else {
				nextVal[i] = j
			}
		} else {
			j = nextVal[j]
		}
	}
}

func IndexKMP(S string, T string) int {
	i, j := 1, 1
	next := make([]int, len(T)+1)
	GetNextVal(T, next)
	for i < len(S) && j < len(T) {
		if j == 0 || S[i] == T[j] {
			i++
			j++
		} else {
			j = next[j]
		}
	}

	if j >= len(T) {
		return i - len(T) + 1
	} else {
		return 0
	}
}

func main() {
	a := "ababcabcacbab"
	b := "abcac"

	c := IndexKMP(a, b)
	fmt.Println(c) // 6
}