串的定义
串，即字符串（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
串的存储结构
定长顺序存储表示
类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值得字符序列。在串的定长顺序存储结构中，为每个串变量分配一个固定长度的存储区，即定长数组。
堆分配存储表示
堆分配存储表示仍然以一组地址连续的存储单元存放串值得字符序列，但它们得存储空间是在程序执行过程中动态分配得到得。
块链存储表示
类似于线性表得链式存储结构，也可采用链表方式存储串值。由于串得特殊性（每个元素只有一个字符），在具体实现时，每个结点即可以存放一个字符，也可以存放多个字符。每个结点称为块，整个链表称为块链结构。
串的基本操作
| 方法 | 描述 |
|---|---|
| StrAssign(&T,chars) | 赋值操作。把串T赋值为chars |
| StrCopy(&T,S) | 复制操作。由串S复制得到串T |
| StrEmpty(S) | 判空操作。若S为空串，则返回TRUE，否则返回FALSE |
| StrCompare(S,T) | 比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0 |
| StrLength(S) | 求串长。返回串S的元素个数 |
| SubString(&Sub,S,pos,len) | 求子串。用Sub返回串S的第pos个字符起长度为len的子串 |
| Concat(&T,S1,S2) | 串联接。用T返回由S1和S2联接而成的新串 |
| Index(S,T) | 定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0 |
| ClearString(&S) | 清空操作。将S清为空串 |
| DestroyString(&S) | 销毁串。将串S销毁（回收存储空间） |
串的模式匹配
简单的模式匹配算法
子串的定位操作通常称为串的模式匹配，它求的是子串（常称模式串）在主串中的位置。这里采用定长顺序存储结构，给出一种不依赖于其他串操作的暴力匹配算法。
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
}