Intro字符串本身不复杂就是一个字符数组。但它引起的问题很多因为字符串是序列序列上可以定义大量不同的操作。1. 为什么学字符串在算法层面字符串排序打破了前面所有排序算法的下界。之前学的归并、快速、堆排序下界都是 N log N因为它们只依赖“比较”操作。但字符串的字符是数字char 本质是整数可以直接用作数组索引。这意味着你可以用键索引计数key-indexed counting做线性时间排序。这是对整个排序理论的一个扩展当键是整数且范围有限时比较排序的下界可以被绕过。在应用层面字符串是信息处理中最基础的抽象。基因组是字符串网页是字符串源代码是字符串日志是字符串。任何需要搜索、匹配、压缩、索引大规模文本的系统底层都是字符串算法。在 EDA/DFT 中网表netlist是字符串的集合门名、线网名、实例名。测试向量test pattern是二进制字符串。日志文件是字符串需要搜索错误模式。故障字典fault dictionary的键是字符串。版图layout中的单元名称是字符串需要排序和查找。扫描链的配置是位字符串。2. 为什么字符串后面还有这么多模块因为字符串上的操作不是一种而是多种每种操作需要不同的数据结构。操作数据结构问题排序字符串LSD、MSD、三路快速排序如何利用字符是整数这个事实做线性时间排序前缀查找Trie如何用字符串的公共前缀来压缩存储和加速查找子串搜索KMP、Boyer-Moore、Rabin-Karp在一段长文本中找一段短模式正则表达式NFA用模式描述一组字符串判断匹配数据压缩Huffman、LZW利用字符串中的冗余减少存储后缀数组后缀排序预处理文本快速回答任意子串查询最长重复子串后缀排序 LCP在字符串中找最长的重复片段这些不是同一个问题的变体而是不同的问题。它们共享“字符串”这个输入类型但操作目标完全不同。3. 为什么感觉“字符串没有这么多东西”因为你之前学的排序、符号表、图每个问题都有清晰的边界排序就是重排数组符号表就是键值映射图就是顶点和边。字符串是一个数据类型不是一个问题。它上面可以定义无限多种操作。你学的是这些操作中最基础、最常用的那些。4. 你接下来会看到的字符串排序5.1利用字符是整数做线性时间排序。Trie5.2用树结构存储字符串集合支持前缀查找。子串搜索5.3在一段文本中找模式串。正则表达式5.4模式匹配。数据压缩5.5Huffman、LZW。这些模块共享同一个核心思想字符串的字符是整数可以直接作为数组索引因此可以利用这个物理事实来设计比通用比较排序更快的算法。5. 对你有用的部分如果你是 DFT/EDA 方向最直接相关的是Trie用于存储和查找网表名称、故障字典。子串搜索用于在日志中找错误模式或在网表中找特定结构。后缀数组用于在版图数据中找重复模式。数据压缩用于压缩测试向量减少测试数据量。字符串排序本身是这些算法的预处理步骤。例如后缀数组需要对所有后缀排序而排序后缀需要高效的字符串排序算法。总结字符串不复杂但字符串上的操作很多。你不需要一口气全部记住。先理解每个模块解决什么问题然后针对你最关心的应用场景EDA/DFT 中的名称查找、模式匹配、测试数据压缩深入。其他的在需要时再查。string in java第 3 页String 定义String字符串是字符的序列。它是信息处理中的基础抽象出现在基因组序列、通信系统、程序源代码等场景。页面引用 Olson 的话说明 DNA 可以表示为 G、A、T、C 组成的字符串。物理上字符串就是一串连续的字符编码每个位置有一个索引。第 4 页C 的 char 与 Java 的 charC 的 char 通常是 8 位整数支持 7 位 ASCII只能表示 256 个字符。页面展示十六进制到 ASCII 的转换表。Java 的 char 是 16 位无符号整数支持最初的 16 位 Unicode后来以别扭的方式支持 21 位 Unicode 3.0。物理含义Java 的 char 占 2 字节能表示 0 到 65535 的码点。对于超出 16 位的 Unicode 字符如 emojiJava 用两个 char 组成代理对surrogate pair来表示。第 5 页Unicode 示例展示一个心形 Unicode 字符。无新物理机制。第 6 页Java String 数据类型的操作String 是字符序列不可变immutable。操作包括length()字符数量。charAt(i)取第 i 个字符。substring(from, to)取连续子序列。concat把一个字符追加到另一个字符串末尾。页面图示s ATTACKATDAWN索引 0 到 11。s.length()返回 12s.charAt(3)返回As.substring(7, 11)返回DAWN。第 7 页Java String 类的内部实现String 类的字段javaprivate char[] value; // 字符数组 private int offset; // 第一个字符在数组中的索引 private int length; // 字符串长度 private int hash; // hashCode() 的缓存方法javapublic int length() { return length; } public char charAt(int i) { return value[i offset]; } private String(int offset, int length, char[] value) { this.offset offset; this.length length; this.value value; } public String substring(int from, int to) { return new String(offset from, to - from, value); }物理事实String 对象本身不直接存储字符数据。它存储一个引用8 字节指向堆上的char[]数组再存储offset4 字节和length4 字节。charAt(i)的物理动作是读取offset加上i用这个索引去value数组取值。substring不复制char[]它创建一个新的 String 对象但新对象的value引用指向同一个底层数组只改变offset和length。所以substring是 O(1) 时间。第 8 页String 操作保证与内存表格length()O(1) 时间O(1) 额外空间。charAt()O(1) 时间O(1) 额外空间。substring()O(1) 时间O(1) 额外空间。concat()O(N) 时间O(N) 额外空间。内存一个长度为 N 的“新” String 使用40 2N字节。物理分解String 对象自身约 40 字节对象头 16 char[]引用 8 offset4 length4 hash4对齐到 40加上char[]中的字符数据每个 char 2 字节共 2N 字节。注意这里没有计算char[]数组对象自身的对象头PPT 把它归入 40 字节或省略了。页面还提到可以使用byte[]或char[]代替 String 来节省空间但失去 String 数据类型的便利。第 9 页StringBuilderStringBuilder 是字符序列可变mutable。底层实现是可扩容的char[]数组和length。对比表操作String 保证String 额外空间StringBuilder 保证StringBuilder 额外空间length()1111charAt()1111substring()11NNconcat()NN1*1**表示摊还amortized。物理事实String 的substring是 O(1)因为共享底层数组。StringBuilder 的substring是 O(N)因为它创建新的 String复制字符。StringBuilder 的append对应 concat是摊还 O(1)因为它在可扩容数组末尾追加字符偶尔扩容时复制整个数组但总代价均摊到每次追加是常数。StringBuffer 类似但线程安全速度更慢。第 10 页反转字符串的效率方法 Ajavapublic static String reverse(String s) { String rev ; for (int i s.length() - 1; i 0; i--) rev s.charAt(i); return rev; }物理动作每次rev ...都会创建一个新的 String 对象复制rev的全部字符和新增字符。第 i 次迭代复制 i 个字符总复制量 12...N O(N²)。二次时间。方法 Bjavapublic static String reverse(String s) { StringBuilder rev new StringBuilder(); for (int i s.length() - 1; i 0; i--) rev.append(s.charAt(i)); return rev.toString(); }物理动作append在 StringBuilder 内部的可扩容数组中追加字符摊还 O(1)。总时间 O(N)。第 11 页字符串挑战——后缀数组问题如何高效地形成后缀数组输入字符串aacaaagtttacaagc索引 0 到 14。列出所有后缀从每个索引 i 开始到字符串末尾的子串。例如索引 0 的后缀是aacaaagtttacaagc索引 1 是acaaagtttacaagc等等。物理事实后缀数组是将一个字符串的所有后缀按字典序排序后得到的索引数组。这一页只展示后缀列表尚未排序。第 12 页形成后缀数组的两种方法方法 Ajavapublic static String[] suffixes(String s) { int N s.length(); String[] suffixes new String[N]; for (int i 0; i N; i) suffixes[i] s.substring(i, N); return suffixes; }物理动作每次s.substring(i, N)创建一个新的 String 对象但底层char[]是共享的按第 7 页的实现。所以创建 N 个 String 对象每个约 40 字节总额外空间 O(N)。字符数据只有一份O(N)。时间 O(N)。页面标注“linear time and linear space”。方法 Bjavapublic static String[] suffixes(String s) { int N s.length(); StringBuilder sb new StringBuilder(s); String[] suffixes new String[N]; for (int i 0; i N; i) suffixes[i] sb.substring(i, N); return suffixes; }物理动作StringBuilder.substring(i, N)返回一个新的 String并且复制字符。第 i 次复制 N-i 个字符总复制量 O(N²)。所以方法 B 的时间是 O(N²)空间也是 O(N²)因为每个后缀都有独立的字符副本。PPT 第 9 页的表格也标明 StringBuilder 的 substring 是 O(N) 时间和 O(N) 额外空间所以 N 次调用是 O(N²)。第 13 页最长公共前缀LCP的计算时间函数javapublic static int lcp(String s, String t) { int N Math.min(s.length(), t.length()); for (int i 0; i N; i) if (s.charAt(i) ! t.charAt(i)) return i; return N; }物理动作从索引 0 开始逐字符比较直到字符不同或到达较短字符串末尾。返回匹配的字符数。运行时间正比于最长公共前缀的长度 D。最坏情况 O(min(len(s), len(t)))典型情况次线性sublinear因为通常很早就遇到不同字符。页面还提到compareTo()也可以在次线性时间内完成。第 14 页字母表Alphabets数字键是固定字母表上的数字序列。基数radixR 是字母表中的数字个数。lgR是表示一个数字所需的比特数。表格名称RlgR字符BINARY210 1OCTAL830-7DECIMAL1040-9HEXADECIMAL1640-9 A-FDNA42A C T GLOWERCASE265a-zUPPERCASE265A-ZPROTEIN205ACDEFGHIKLMNPQRSTVWYBASE64646A-Z a-z 0-9 /ASCII1287ASCII 字符EXTENDED_ASCII2568扩展 ASCII 字符UNICODE6553616Unicode 字符物理含义R 决定了基数排序中“桶”的数量。例如 DNA 的 R4每个字符有 4 种可能可以用 2 位表示ASCII 的 R128每个字符 7 位Unicode 的 R65536每个字符 16 位。后续的键索引计数key-indexed counting和基数排序radix sort会使用 R 作为数组大小来统计频率和分配位置。这一节的核心物理线索Java 的 String 是不可变对象内部持有一个char[]的引用、offset和length。substring共享底层数组所以 O(1)。String的拼接会创建新对象并复制字符所以循环拼接是 O(N²)。StringBuilder用可扩容数组append摊还 O(1)但substring会复制。后缀数组的构造可以利用String.substring的共享特性达到线性额外空间但用StringBuilder.substring会退化到 O(N²)。字母表基数 R 是后续字符串排序算法的基础参数。QsQ这里Immutable和mutable的string我都没有太看懂尤其是这个concat是做什么用的为什么immutable的substring需要n这里讲的需要n是什么指的是substring会返回一个东西然后返回的这个东西所占用的空间是n吗那么为什么mutable的substring会变成一呢这里是n和是一的到底是什么A这张表把两种字符串类型放在一起对比不可变 String和可变 StringBuilder。你问的 n 和 1是两项指标guarantee是时间保证extra space是额外空间。1. Immutable 和 Mutable 是什么Immutable不可变对象一旦在堆上创建它内部的字符数据就不能被修改。你无法改变某个索引上的字符也无法在末尾追加字符。任何“看起来像修改”的操作拼接、截取都会创建一个新的 String 对象原来的对象保持不变。Mutable可变对象内部的字符数组可以被修改。你可以在末尾追加字符append可以改变某个索引上的字符不需要创建新对象。2. concat 是什么concat是字符串拼接把两个字符串的字符首尾相连组成一个新的字符串。物理动作在堆上创建一个新的char[]数组长度等于两个字符串长度之和。把第一个字符串的所有字符复制到新数组的前半部分。把第二个字符串的所有字符复制到新数组的后半部分。创建一个新的 String 对象指向这个新数组。所以拼接的代价正比于结果字符串的总长度 N。这就是为什么concat()那一行写的是 N时间 O(N)额外空间 O(N)。3. 为什么 immutable 的 substring 是 1看第 7 页的 String 内部实现javaprivate char[] value; // 底层字符数组 private int offset; // 从数组的哪个索引开始 private int length; // 取多少个字符substring(from, to)的物理动作是javareturn new String(offset from, to - from, value);它不复制char[]。它只是创建一个新的 String 对象新对象里的value引用指向同一个底层数组只改变offset和length。让char[] value指向同一个数组不需要额外创建一个char[]再写东西进去了所以时间O(1)只创建了一个小对象约 40 字节不复制字符。额外空间O(1)新对象的大小与 N 无关始终是常数。表中的 1 就是常数。它不是指“返回的内容大小为 1”而是指“这个操作的代价是常数与字符串长度无关”。4. 为什么 mutable 的 substring 是 N看第 9 页 StringBuilder 的实现底层是可扩容的 char[] 数组加一个 length。StringBuilder.substring(from, to)不能像 String 那样共享底层数组。原因StringBuilder 的数组后续可能被修改比如 append 会改变内容如果共享新的 String 对象就会“看到”后续的修改这破坏了 String 的不可变性。所以 StringBuilder 的 substring 必须复制字符到一个新的char[]再创建 String 对象。复制 N 个字符时间和额外空间都是 O(N)。5. 为什么 mutable 的 concatappend是 1StringBuilder 的append物理动作如果内部数组还有空位直接在末尾写入字符length。O(1)。如果数组满了创建一个更大的数组通常是两倍复制旧字符再写入新字符。扩容不常发生。把扩容的代价均摊到每次 append 上平均是 O(1)。这叫摊还amortized代价。表中的 1 带星号就是这个意思。6. 总结对比操作String不可变StringBuilder可变substring共享底层数组O(1) 时间、O(1) 空间必须复制字符O(N) 时间、O(N) 空间concat/append必须创建新数组并复制O(N) 时间、O(N) 空间在末尾追加摊还 O(1) 时间、O(1) 空间表中的 n 就是字符串长度 N。1 就是常数与 N 无关。你之前把 immutable 的 substring 和 mutable 的 substring 看反了immutable 的 substring 是 1mutable 的 substring 是 N。