数据结构：
串-字符串
栈
线性表
经典排序算法 上篇
经典排序算法 下篇
串–字符串
一，前言
串是由零个或多个字符组成的有限序列，又名字符串。
-
空字符串
零个字符的串就是空串。也就是常说的 “”
二，串的比较
- 字符串的比较实际是比较字符的值，根据不同的编码进行存储，最初的ASCII 到 Unicode。从最初的128个字符，到65w多。
- 字符串的长度一样，每一个相对位置的字符值都一样，就可以说这两个字符串是相等的。
三，串的顺序存储结构
就是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的串的大小为串变量分配一个固定长度的存储区。一般是用定长数组来定义。
缺点：
- 两个串进行拼接，新串的插入，以及字符串的替换操作都有可能使得串的长度超过数组的长度。
- 如果溢出就会出现字符串被截断的问题。
四，串的链式存储结构
就是用链表来存储串的内容。
缺点：
- 虽然解决了顺序存储的空间问题，但是每个node存储字符多少合适不好考量，因为会直接影响处理效率。
- 总的来说灵活性没有顺序结构，性能也不如顺序结构。
五，字符串匹配
1，朴素的字符串匹配
字符串 S 匹配串 T
简单总结就是S做大循环，每个字符进行T的小循环。
举一个极端的例子。S=“00000000000000000000000000000000000000001” T=“0000001”。
T 的0越多，循环次数越多。
2，KMP匹配算法
KMP算法，是三个人参与的算法，我们称之为 克努特-莫里斯-普拉特算法
算法的关键在于，分析匹配串的每个字符串的位置和匹配初始位置。
golang实现：
// KMP 匹配算法
func KMP(s, t string, pos int) int {
i := pos
j := 1
next := getNextval(t)
slen := len(s)
tmplen := len(t)
for i < slen && j < tmplen {
if j == 0 || s[i] == t[j] {
i++
j++
} else {
j = next[j]
}
}
if j == tmplen {
return i - tmplen
} else {
return 0
}
}
// 根据匹配串得出匹配开始位置
func getNext(t string) []int {
var i, j int
i = 1
j = 0
next := make([]int, len(t)+1)
for i < len(t) && j < len(t) {
if j == 0 || t[i] == t[j] {
i++
j++
next[i] = j
} else {
j = next[j]
}
}
return next
}
// 根据匹配串得出匹配开始位置 优化版
func getNextval(t string) []int {
var i, j int
i = 1
j = 0
next := make([]int, len(t)+1)
for i < len(t) && j < len(t) {
if j == 0 || t[i] == t[j] {
// next[i] = j
if t[i] != t[j] {
next[i] = j
} else {
next[i] = next[j]
}
i++
j++
} else {
j = next[j]
}
}
return next
}
测试结果：
tem: ABACAABAC
getNext(t): [0 0 1 1 1 1 1 2 3 4]
PASS
s: afeincseifnsliwneit
tmp: fnsliwn
KMP(s, t, 0): 9
PASS
六，总结
字符串的循环累加，会消耗大量的空间，一般语言会实现字符串的累加优化。下期针对字符串的累加优化进行golang的学习。
|