数值结构之字符串 String

I. 串

1. 什么是串

串 String：

  • 由零个或多个字符组成的有限序列，又叫字符串
  • 一般记为 s = "a0a1...an-1"
  • ai 可以是字母、数字或者其他字符，i 是该字符在串中的索引
  • 串的长度： n，是一个有限的数值
  • 空串：null string，长度为0, 记做 ""

还有几个概念：

  • 子串：串中任意个数的连续字符组成的子序列称为该串的子串
  • 主串： 包含子串的串就是主串
  • 子串在主串中的位置就是子串的第一个字符在主串中的索引

2. 串的比较

给定两个串： s = "a0a1a2...an-1" 和 t = "b0b1b2...bm-1", 当满足以下条件之一时， s < t

  • n < m, 且 ai = bi (i = 0, 1, 2, …, n-1)
    • 比如 s = “hap” , t = “happy”, 则 s < t, 因为 t 比 s 多出两个字符
  • 存在某个 k <= min(m, n), 使得 ai = bi (i = 0, 1, 2, …., k-1), ak < bk
    • 比如当 s = “happen”, t = “happy”, 两个串前 4 个字母都相同，而两个串第 5 个字母 （k值）， e 的 ASCII 码小于 y， 所以 e < y， 所以 s < t

II. 串的实现

串的逻辑结构和线性表相似，不同之处是串中的元素都是字符，所以串的基本操作和线性表有很大差别。

  • 线性表更关注单个元素的操作，比如查找一个元素，插入或者删除一个元素
  • 串更关注查找子串位置，得到指定位置子串，替换子串等操作

1. 串的抽象数据类型

ADT string
Data
	串中元素仅由一个字符组成，相邻元素具有前驱和后继关系
Operation
	StrAssign(T, *chars)			// 生成一个值为字符串常量 chars 的串 T
	StrCopy(T, S)					// 串 s 存在，由串 S 复制得到串 T
	ClearString(S)					// 串 s 存在，将串清空
	StringEmpty(S)					// S 为空返回 true，否则 false
	StrLength(S)					// 返回串 S 的元素个数，即长度
	StrCompare(S, T)				// 若 S > T, 返回 >0; S = T, 返回 0; S < T, 返回 <0
	Concat(T, S1, S2)				// 用 T 返回连接 S1 和 S2 的新串
	SubString(sub, S, pos, len)		// 用 sub 返回 s 的第 pos 个字符起，长度为 len 的子串
	Index(S, T, pos)				// 若主串 S 中存在和串 T 值相同的子串，则返回它在主串第 pos个字符之后第一次出现的位置，否则返回 0
	Replace(S, T, V)				// 用 V 替换主串 S 中出现的所有与T相等的不重叠的字符串
	StrInsert(S, pos, T)			// 在串 S 的第 pos个字符之前插入串 T
	StrDelete(S, pos, len)			// 从串 S 中删除第 pos 个字符起，长度为 len 的子串
endADT

2. 串的顺序存储结构

串的顺序存储结构：

  • 是用一组地址连续的存储单元来存储串中的字符序列的
  • 按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，一般用定长数组来定义

但是用定长数组有一个问题，就是如果进行了 replace 或者 insert 操作等，字符串长度可能会超过最大数组长度从而造成溢出

3. 串的链式存储结构

串的链式存储结构和线性表相似，但是串结构中每个元素数据，可能是一个字符，也可能存放多个字符。

串的链式存储结构除了在连接串与串之间的操作比顺序表方便之外，总的来说不如顺序存储灵活，性能也不如顺序存储结构好

III. 模式匹配算法

子串的定位操作通常称作串的模式匹配，是串中最重要的操作之一

1. 朴素模式匹配算法

简单来说，就是对主串的每一个字符作为子串的开头，与要匹配的字符串进行匹配，对主串做大循环，每个字符开头做 T 的长度的小循环 ，直到匹配成功或全部遍历完成为止。

我们假设主串 S 和要匹配的子串 T，实现代码如下：

public static int index(String s, String t, int pos){
	// i 用于记录主串遍历的起点
	int i = pos;
	// j 用于记录子串遍历的起点
	int j = 0;

	// 遍历主串和子串
	while(i<s.length() && j < t.length()){
		// 如果主串和子串的字符相同
		if(s.charAt(i) == t.charAt(j)){
			++i;
			++j;
		}else{
		// 主串和子串不匹配，主串指针退回到上次匹配的首位的下一位
			i = i - j +1;
			j = 0; // 子串从头开始
		}
	}

	if(j > 0)
		// 匹配到子串，j 在子串的末尾，i 在主串中包含子串的末尾
		// 二者相减，得到子串第一个字符在主串中的位置
		return i - j;
	else
		// 否则，返回 0
		return 0;
}

这个算法效率太低，所以介绍一个 KMP 模式匹配算法

2. KMP 模式匹配算法

KMP 模式匹配算法是为了避免朴素算法的重复遍历的情况，先来看 KMP 算法的原理

至于 KMP 模式匹配算法的原理，参见从头到尾彻底理解KMP

Share this on