Java医院住院系统源码解析：业务逻辑与工程实践
2026/10/5 3:10:21
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）：利用字符是整数，做线性时间排序。
Trie（5.2）：用树结构存储字符串集合，支持前缀查找。
子串搜索（5.3）：在一段文本中找模式串。
正则表达式（5.4）：模式匹配。
数据压缩（5.5）：Huffman、LZW。
这些模块共享同一个核心思想：字符串的字符是整数，可以直接作为数组索引，因此可以利用这个物理事实来设计比通用比较排序更快的算法。
5. 对你有用的部分
如果你是 DFT/EDA 方向，最直接相关的是：
Trie：用于存储和查找网表名称、故障字典。
子串搜索：用于在日志中找错误模式，或在网表中找特定结构。
后缀数组：用于在版图数据中找重复模式。
数据压缩：用于压缩测试向量，减少测试数据量。
字符串排序本身是这些算法的预处理步骤。例如，后缀数组需要对所有后缀排序，而排序后缀需要高效的字符串排序算法。
总结
字符串不复杂，但字符串上的操作很多。你不需要一口气全部记住。先理解每个模块解决什么问题，然后针对你最关心的应用场景（EDA/DFT 中的名称查找、模式匹配、测试数据压缩）深入。其他的在需要时再查。
string in java
第 3 页：String 定义
String（字符串）是字符的序列。它是信息处理中的基础抽象，出现在基因组序列、通信系统、程序源代码等场景。页面引用 Olson 的话，说明 DNA 可以表示为 G、A、T、C 组成的字符串。物理上，字符串就是一串连续的字符编码，每个位置有一个索引。
第 4 页：C 的 char 与 Java 的 char
C 的 char 通常是 8 位整数，支持 7 位 ASCII，只能表示 256 个字符。页面展示十六进制到 ASCII 的转换表。
Java 的 char 是 16 位无符号整数，支持最初的 16 位 Unicode，后来以别扭的方式支持 21 位 Unicode 3.0。物理含义：Java 的 char 占 2 字节，能表示 0 到 65535 的码点。对于超出 16 位的 Unicode 字符（如 emoji），Java 用两个 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()返回 12，s.charAt(3)返回A，s.substring(7, 11)返回"DAWN"。第 7 页：Java String 类的内部实现
String 类的字段：
java
private char[] value; // 字符数组 private int offset; // 第一个字符在数组中的索引 private int length; // 字符串长度 private int hash; // hashCode() 的缓存方法：
java
public 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[]数组，再存储offset（4 字节）和length（4 字节）。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 页：StringBuilder
StringBuilder 是字符序列，可变（mutable）。底层实现是可扩容的
char[]数组和length。对比表：
操作 String 保证 String 额外空间 StringBuilder 保证 StringBuilder 额外空间 length() 1 1 1 1 charAt() 1 1 1 1 substring() 1 1 N N concat() N N 1* 1*
*表示摊还（amortized）。物理事实：
String 的
substring是 O(1)，因为共享底层数组。StringBuilder 的
substring是 O(N)，因为它创建新的 String，复制字符。StringBuilder 的
append（对应 concat）是摊还 O(1)，因为它在可扩容数组末尾追加字符，偶尔扩容时复制整个数组，但总代价均摊到每次追加是常数。StringBuffer 类似，但线程安全，速度更慢。
第 10 页：反转字符串的效率
方法 A：
java
public 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 个字符，总复制量 1+2+...+N = O(N²)。二次时间。方法 B：
java
public 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 页：形成后缀数组的两种方法
方法 A：
java
public 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”。方法 B：
java
public 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）的计算时间
函数：
java
public 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）
数字键是固定字母表上的数字序列。基数（radix）R 是字母表中的数字个数。
lgR是表示一个数字所需的比特数。表格：
名称 R lgR 字符 BINARY 2 1 0 1 OCTAL 8 3 0-7 DECIMAL 10 4 0-9 HEXADECIMAL 16 4 0-9 A-F DNA 4 2 A C T G LOWERCASE 26 5 a-z UPPERCASE 26 5 A-Z PROTEIN 20 5 ACDEFGHIKLMNPQRSTVWY BASE64 64 6 A-Z a-z 0-9 + / ASCII 128 7 ASCII 字符 EXTENDED_ASCII 256 8 扩展 ASCII 字符 UNICODE 65536 16 Unicode 字符 物理含义：R 决定了基数排序中“桶”的数量。例如 DNA 的 R=4，每个字符有 4 种可能，可以用 2 位表示；ASCII 的 R=128，每个字符 7 位；Unicode 的 R=65536，每个字符 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 是后续字符串排序算法的基础参数。
Qs
Q：这里，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 内部实现：
java
private char[] value; // 底层字符数组 private int offset; // 从数组的哪个索引开始 private int length; // 取多少个字符
substring(from, to)的物理动作是：java
return 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 的 concat（append）是 1
StringBuilder 的
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 是 1，mutable 的 substring 是 N。