---
marp: true
theme: kurzus
paginate: true
footer: 数据结构 · 第 4 周 · 字符串
---

<!-- _class: cim -->
<!-- _paginate: false -->
<!-- _footer: "" -->

# 数据结构

## 第 4 周 – 字符串：表示、编码、操作、模式匹配

Koczka Ferenc 博士 · 埃斯特哈齐·卡罗伊大学 · 2026

---

## 复习

- 数组是<strong>同构、静态、顺序存储、直接访问</strong>的
- 地址计算 → 访问 <strong>O(1)</strong> · 在中间插入/删除 <strong>O(n)</strong>
- <strong>动态数组：</strong>容量加倍 → 追加操作均摊 O(1)

### 今天的问题

- 机器如何存储文本 – 为什么 `len("世界") == 6`？
- 为什么在循环中用 `+` 拼接很慢？
- 怎样在文本中找到一个词？

<!--
时间安排：概念、表示 15' · 编码 20' · 不可变性、操作 25' · 模式匹配 20' · 小结 10'
-->

---

## 字符串的概念

<strong>字符串</strong>（字符串、文本）是字符的有限序列。

- 本质上是一个<strong>字符数组</strong> – 再加上针对文本的操作
- <strong>长度：</strong>字符的个数 · <strong>空串：</strong>`""`（长度为 0）
- <strong>子串：</strong>连续的一段字符（`"data"` 是 `"database"` 的一部分）

| 性质 | 字符串 |
|---|---|
| 元素 | 同构（字符） |
| 存储 | 顺序 |
| 访问 | 直接（按下标） |
| 可变性 | Java、Go：<strong>不可变</strong> |

---

## 表示方法

![w:1000](kepek/h04_abrazolas.svg)

---

<!-- _class: fejezet -->

# 字符编码

---

## ASCII、Unicode、UTF-8

- <strong>ASCII</strong>(1963):7 位，128 个字符 – 英文字母、数字、标点
- <strong>Unicode：</strong>为每一种文字的每一个字符分配一个编号，即<strong>码点</strong>
  `A` = U+0041 · `é` = U+00E9 · `世` = U+4E16 · `😀` = U+1F600
- 码点必须转换成字节：这就是<strong>编码</strong>

| 编码 | 一个字符的大小 | 使用者 |
|---|---|---|
| <strong>UTF-8</strong> | 1–4 字节（ASCII = 1 字节） | Web、Linux、<strong>Go</strong> |
| <strong>UTF-16</strong> | 2 或 4 字节 | <strong>Java</strong>、Windows、JavaScript |
| UTF-32 | 固定 4 字节 | 很少使用 |
| GB 2312 / GBK / GB 18030 | 1–4 字节 | 中国国家标准 |

---

## UTF-8：变长编码

![w:1000](kepek/h04_utf8.svg)

<div class="doboz figyelem">

“有多少个字符？”的答案取决于我们数的是什么：<strong>字节</strong>、<strong>UTF-16 单元</strong>还是<strong>码点</strong>。

</div>

---

<!-- _class: kicsi -->

## Java 和 Go 中的字符

<div class="ket-hasab">
<div>

<span class="cimke java">Java – UTF-16</span>

```java
String s = "Aé世😀";
s.length();                  // 5(char)
s.codePointCount(0, s.length()); // 4
s.charAt(2);                 // '世'
s.getBytes(UTF_8).length;    // 10

// 按码点遍历:
s.codePoints().forEach(cp -> ...);
```

- `char` = 16 位 → 一个表情符号占<strong>两个</strong> `char`（代理对）
- 大多数汉字占<strong>一个</strong> `char`

</div>
<div>

<span class="cimke go">Go – UTF-8</span>

```go
s := "Aé世😀"
len(s)                      // 10(字节!)
utf8.RuneCountInString(s)   // 4
s[2]                        // 0xA9 – 一个字节!
[]rune(s)[2]                // '世'

for i, r := range s {       // 逐个 rune
    fmt.Printf("%d %c\n", i, r)
}
```

- `s[i]` 得到一个<strong>字节</strong>，`range` 得到一个 <strong>rune</strong>
- 需要逐字符处理时：`[]rune(s)`

</div>
</div>

---

## 字符运算

英文字母和数字的编码是<strong>连续</strong>的：

| | 编码 | 推论 |
|---|---|---|
| `'0'` … `'9'` | 48 … 57 | 数字的值：`c - '0'` |
| `'A'` … `'Z'` | 65 … 90 | 字母的序号：`c - 'A'` |
| `'a'` … `'z'` | 97 … 122 | 小写 → 大写：`c - 32` |

```java
int digit = '7' - '0';                   // 7
char upper = (char) ('g' - ('a' - 'A')); // 'G'
int[] freq = new int[26];
freq[c - 'a']++;                         // 字母频率
```

<div class="doboz tipp">

用 26 个元素的数组统计字母频率很简单，但只适用于英文字母。一般情况下我们使用<strong>哈希表</strong>（第 11 周）。

</div>

---

<!-- _class: fejezet -->

# 字符串操作

---

## 不可变的字符串

在 Java 和 Go 中，字符串的内容<strong>创建之后就不能改变</strong>。

```java
String s = "hello";
s.toUpperCase();          // 返回一个新字符串,s 不变!
s = s.toUpperCase();      // 应该这样写
```

<strong>优点：</strong>

- 可以安全地共享（在变量之间、在线程之间）
- 可以用作哈希表的键
- Java：<strong>字符串常量池</strong>中相同的字面量只存一份

<strong>缺点：</strong>每次“修改”都会创建新字符串 → <strong>复制</strong>

---

## 在循环中拼接：O(n²)！

<div class="ket-hasab">
<div>

```java
// 慢 – O(n²)
String s = "";
for (int i = 0; i < n; i++)
    s += "x";   // 新字符串 + 复制
```

```java
// 快 – O(n)
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++)
    sb.append("x");
String s = sb.toString();
```

Go:`strings.Builder` · `sb.WriteString("x")`

</div>
<div>

| n | `+=` | Builder |
|---|---|---|
| 10 000 | 10 ms | 0.05 ms |
| 40 000 | 46 ms | 0.08 ms |
| 160 000 | 624 ms | 0.4 ms |

<span class="halvany">（Go，实测值）</span>

`StringBuilder` 内部是一个<strong>动态数组</strong>（第 3 周） – 追加操作均摊 O(1)。

</div>
</div>

---

## 比较

<strong>字典序：</strong>从左往右逐个字符比较，第一个不同的字符决定大小；如果一个是另一个的前缀，较短的那个较小。

```text
Function Compare(S, T)                // −1、0 或 1
  i ← 1
  While i ≤ length(S) and i ≤ length(T) and S[i] = T[i]
    i ← i + 1
  End while
  If i ≤ length(S) and i ≤ length(T) then
    If S[i] < T[i] then Return −1 else Return 1
  else if length(S) = length(T) then Return 0
  else if length(S) < length(T) then Return −1
  else Return 1
End function
```

`"apple" < "apply"` · `"data" < "database"` · `"Zebra" < "apple"`（大写字母的编码更小！）

---

## Java 中的常见错误：`==` 与 `equals`

```java
String a = "data";
String b = "data";               // 同一个对象(常量池)
String c = new String("data");   // 一个新对象

a == b          // true  – 纯属巧合!
a == c          // false – 不同的对象
a.equals(c)     // true  – 内容相等
```

<div class="doboz figyelem">

在 Java 中比较字符串<strong>一律使用 `equals`</strong>。`==` 比较的是<strong>引用</strong>（第 1 周）。

</div>

在 Go 中 `==` 比较的是<strong>内容</strong>：`a == c` → `true`

---

<!-- _class: kicsi -->

## 操作：Java 和 Go

| 操作 | Java | Go | 步数 |
|---|---|---|---|
| 长度 | `s.length()` | `len(s)`（字节） | O(1) |
| 第 i 个字符 | `s.charAt(i)` | `s[i]`（字节） | O(1) |
| 子串 | `s.substring(a, b)` | `s[a:b]` | O(b−a) / O(1)* |
| 拼接 | `s + t`、`s.concat(t)` | `s + t` | O(n + m) |
| 相等 | `s.equals(t)` | `s == t` | O(n) |
| 比较 | `s.compareTo(t)` | `s < t`、`strings.Compare` | O(n) |
| 查找 | `s.indexOf(t)` | `strings.Index(s, t)` | O(n · m)** |
| 分割 | `s.split(",")` | `strings.Split(s, ",")` | O(n) |
| 替换 | `s.replace(a, b)` | `strings.ReplaceAll(s, a, b)` | O(n) |
| 大小写转换 | `toLowerCase()`、`toUpperCase()` | `strings.ToLower`、`ToUpper` | O(n) |

<span class="halvany">* Go 中取子串不复制，而是引用共享的字节。 ** 类库中也使用更聪明的算法。</span>

---

<!-- _class: kicsi -->

## 经典问题：回文

<strong>回文：</strong>正着读和倒着读都一样 – `"radar"`、`"上海自来水来自海上"`

<div class="ket-hasab">
<div>

<span class="cimke pszeudo">伪代码</span>

```text
Function Palindrome(S, n)
  i ← 1 ; j ← n
  While i < j and S[i] = S[j]
    i ← i + 1
    j ← j − 1
  End while
  Return i ≥ j
End function
```

两个下标相向移动 – <strong>O(n)</strong>,O(1) 空间。

</div>
<div>

<span class="cimke go">Go – 支持 Unicode</span>

```go
func isPalindrome(s string) bool {
    r := []rune(s)
    for i, j := 0, len(r)-1; i < j;
            i, j = i+1, j-1 {
        if r[i] != r[j] {
            return false
        }
    }
    return true
}
```

<div class="doboz figyelem">

如果在 Go 中逐字节检查，这段中文就<strong>不是</strong>回文了！

</div>

</div>
</div>

<!--
上海自来水来自海上 – 一个著名的中文回文句。
-->

---

<!-- _class: fejezet -->

# 模式匹配

---

## 模式匹配问题

<strong>已知：</strong>长度为 <em>n</em> 的<strong>文本</strong>（S）和长度为 <em>m</em> 的<strong>模式</strong>（P），m ≤ n。
<strong>任务：</strong>P 在 S 中第一次出现在哪里？

应用：文本编辑器的“查找”功能、`grep`、病毒扫描、<strong>DNA 序列</strong>分析、抄袭检测

<strong>朴素（暴力）算法：</strong>

- 尝试模式的每一个可能的起始位置：i = 1, 2, …, n − m + 1
- 在每个位置逐个字符地比较模式和文本
- 一旦不匹配，就移到下一个位置

---

## 朴素模式匹配 – 示例

![w:880](kepek/h04_naiv.svg)

总共 <strong>7</strong> 次字符比较

---

<!-- _class: kicsi -->

## 朴素模式匹配 – 算法

<div class="ket-hasab">
<div>

<span class="cimke pszeudo">伪代码</span>

```text
Function NaiveSearch(S, n, P, m)
  For i ← 1 to n − m + 1
    j ← 1
    While j ≤ m and S[i + j − 1] = P[j]
      j ← j + 1
    End while
    If j > m then Return i
  End for
  Return 0
End function
```

</div>
<div>

<span class="cimke java">Java</span>

```java
static int naiveSearch(String s, String p) {
    int n = s.length(), m = p.length();
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        while (j < m &&
               s.charAt(i + j) == p.charAt(j))
            j++;
        if (j == m) return i;
    }
    return -1;
}
```

</div>
</div>

---

## 朴素算法的效率

- <strong>最好情况：</strong>模式在开头 → O(m)
- <strong>最坏情况：</strong>在每个位置都几乎匹配到最后
  S = `aaaa…aab`(n = 10 001),P = `aa…ab`(m = 101)
  → <strong>1 000 001</strong> 次比较 ≈ n · m → <strong>O(n · m)</strong>
- 在自然语言文本中通常在前 1–2 个字符就发现不匹配 → 实际上很快

### 更高效的算法（仅作介绍）

- <strong>KMP(Knuth–Morris–Pratt):</strong>O(n + m) – 利用模式本身的结构，文本指针从不回退
- <strong>Boyer–Moore：</strong>从右往左比较，可以大步跳跃 – 实际中非常快
- <strong>Rabin–Karp：</strong>比较哈希值（第 11 周）

---

## 小结

- 字符串是<strong>字符序列</strong>，顺序存储，直接访问
- 编码：<strong>Unicode</strong> 码点 → <strong>UTF-8</strong>（Go、Web）或 <strong>UTF-16</strong>(Java)
- “长度”可以指字节数、UTF-16 单元数或码点数 – Go 中 `len(s)` 给出的是字节数！
- Java 和 Go 的字符串是<strong>不可变</strong>的 → 在循环中使用 `StringBuilder` / `strings.Builder`
- Java 中要用 `equals`，不要用 `==`！
- <strong>朴素模式匹配：</strong>最坏情况 O(n · m)；更好的算法：KMP、Boyer–Moore

<strong>下周：</strong>排序 I – 冒泡排序、选择排序和插入排序。

---

## 复习题

1. Go 中 `len("中国")` 的值是多少？Java 中 `"中国".length()` 呢？
2. 判断对错：在 Java 中调用 `s.toUpperCase()` 之后，`s` 就变成大写了。
3. 为什么下面的代码是 O(n²) 的？`for (...) s += "x";`
4. `"data"` 和 `"Data"` 哪个的字典序更小？为什么？
5. 对 `S = "AAAAA"` 和 `P = "AAB"`，朴素算法进行多少次字符比较？
6. Java 输出什么：`new String("go") == "go"`？

<!--
答案：1. Go:6（2 × 3 字节），Java:2  2. 错 – 它返回一个新字符串，s 不变
3. 每次 += 都创建一个新字符串并复制已有的全部内容：1 + 2 + … + n = O(n²)
4. "Data" – 'D' = 68 < 'd' = 100   5. 位置 i=0,1,2 → 每个位置 3 次比较（A=A, A=A, A≠B）→ 9
6. false – 不同的对象（equals 会给出 true）
-->

---

<!-- _class: fejezet -->
<!-- _footer: "" -->

# 实践课

---

<!-- _class: gyak -->

## 示例程序

| 程序 | Java | Go | 演示内容 |
|---|---|---|---|
| 基础 | `StringBasics.java` | `w04/stringbasics` | 各种操作、`==` 与 `equals`、比较 |
| 编码 | `Encoding.java` | `w04/encoding` | 字节、`char`、码点、UTF-8 字节 |
| Builder | `Builder.java` | `w04/builder` | `+=` 与 `StringBuilder` 的计时 |
| 模式匹配 | `PatternSearch.java` | `w04/patternsearch` | 朴素查找、所有出现位置、最坏情况 |

---

<!-- _class: gyak -->

## 练习

1. <strong>回文：</strong>判断一个句子是否是回文（忽略大小写和标点）！（`"A man, a plan, a canal: Panama"` ✓）
2. <strong>单词计数：</strong>如果单词之间用一个或多个空格分隔，文本中有多少个单词？
3. <strong>字母频率：</strong>用 26 个元素的数组统计英文字母出现的次数！
4. <strong>凯撒密码：</strong>把字母移动 <em>k</em> 位（`"Hello" → "Khoor"`,k = 3），再解密！
5. <strong>变位词：</strong>两个单词是否由相同的字母组成？（`listen` – `silent`）
6. <strong>压缩：</strong>`"aaabbcdddd" → "a3b2c1d4"`
7. <strong>单词逆序：</strong>`"I love data structures" → "structures data love I"`

参考答案：`Exercises04.java`、`w04/exercises`

---

<!-- _class: gyak -->

## 课后作业

1. <strong>不使用库函数</strong>实现字典序比较（返回 `-1`、`0`、`1`）！
2. 编写函数，返回模式<strong>所有</strong>出现位置的起始下标 – 包括重叠的出现！（在 `"aaaa"` 中找 `"aa"`:0、1、2）
3. 编写程序，输出文本中<strong>出现次数最多</strong>的单词！（提示：Java `HashMap<String,Integer>`,Go `map[string]int`。）
4. 用 Go 编写函数，把字符串逆序，并且让汉字和表情符号也能正确显示！

<!--
解题思路：
1. 见幻灯片上的 Compare 伪代码。
2. 朴素查找，但匹配之后不停止，而是从 i+1 继续。
3. words = split;map[word]++；然后在 map 上求最大值。
4. r := []rune(s)；用两个下标逆置；string(r)。
-->