字符识别

GitHub跳转原题关系图返回列表

基于行汉明距离预处理与线性动态规划的字符切分与识别

OJ: roj

题目 ID: 2088

难度:提高+/省选-

标签:动态规划线性DP位运算

创建: 2026-10-01 07:57

更新: 2026-10-07 13:50

形式化题目

给定字符集 $\Sigma$ 包含 27 个字符（空格及 26 个小写英文字母），每个字符由 $20 \times 20$ 的 01 矩阵（字模）表示。

给定由 $N$ 行长为 20 的 01 串构成的图像序列。该序列由未知字符序列依次拼接而成，但在传输中每个字符均可能发生行损坏与位翻转：

每个字符的行数可能为 19（恰好缺失一行）、20（行数未变）或 21（恰好有一行被重复一次，且重复行紧随其后）。
当某行被重复为两行时，该行与字模对应行之间的差异仅按两者中差异较小的一行计算。
图像序列中某些位置的位可能发生反转（ $0 \leftrightarrow 1$ ）。

求一种将输入序列完整分割为连续字符图案的方案，使得所有字符图案与对应标准字模的总位差异（汉明距离）最小，输出识别出的字符序列。

正解

思路

本题是典型的线性序列划分动态规划问题。

1. 状态定义

设 $dp[i]$ 表示成功识别并匹配输入前 $i$ 行图像时的最小总错误位代价。
因为每个字符在受损后占用的行数只可能是 $19$ 、 $20$ 或 $21$ 行，因此到达状态 $i$ 只能由以下三种前驱状态转移而来：

$dp[i - 19]$ ：当前字符发生了缺失行错误，占 $19$ 行；
$dp[i - 20]$ ：当前字符未发生行增删，占 $20$ 行；
$dp[i - 21]$ ：当前字符发生了重复行错误，占 $21$ 行。

2. 行间汉明距离预处理

每行图像均为 $20$ 位的 01 串，可以将其压缩为一个整数。两行的位差异数即为两整数按位异或后的二进制中 $1$ 的个数（内置 bit_count()）。
预处理三维数组 $diff[i][c][r]$ ，表示输入序列的第 $i$ 行与字符 $c$ 的字模第 $r$ 行之间的汉明距离。

3. 三种长度的匹配代价计算

对于输入的区间 $[i, i + L - 1]$ （其中 $L \in \{19, 20, 21\}$ ）和候选字符 $c$ ：

正常匹配（ $L = 20$ ）：
每一行一一对应：
$\text{cost} = \sum_{r=0}^{19} diff[i+r][c][r]$
缺失一行（ $L = 19$ ）：
枚举字模中被遗漏的行号 $k \in [0, 19]$ 。输入的前 $k$ 行对应字模的前 $k$ 行，输入的后 $19 - k$ 行对应字模的第 $k+1 \dots 19$ 行：
$\text{cost}(k) = \sum_{r=0}^{k-1} diff[i+r][c][r] + \sum_{r=k}^{18} diff[i+r][c][r+1]$
随着 $k$ 从 $0$ 递增到 $18$ ，每次更新只需 $O(1)$ 的增量调整，从而在 $O(20)$ 内求出 $\min_{k} \text{cost}(k)$ 。
重复一行（ $L = 21$ ）：
枚举字模中被重复复制的行号 $k \in [0, 19]$ 。输入中第 $k$ 行与第 $k+1$ 行均来源于字模第 $k$ 行，根据题意只计算损坏较小的那一行：
$\min(diff[i+k][c][k], diff[i+k+1][c][k])$
其他行保持对应关系。利用前后缀和数组，对每个 $k$ 可在 $O(1)$ 时间内计算出代价，总计 $O(20)$ 求出最优重复行。

4. 路径回溯

在 DP 过程中用 prev 数组记录使得 $dp[i]$ 取得最小值的转移前驱位置与识别出的字符。DP 结束后，从 $N$ 出发逆向回溯，即可还原出完整的识别文本。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47

import sys

INF = 10**9
CHARS = " abcdefghijklmnopqrstuvwxyz"


def calc_diff19(dc: list[list[int]]) -> tuple[int, int]:
    """计算 19 行输入与标准字体匹配时的最小差异及最优字符编号。"""
    best_cost, best_c = INF, 0
    for c in range(27):
        d = dc[c]
        # 缺失第 k 行：前 k 行匹配标准第 0..k-1 行，后 19-k 行匹配标准第 k+1..19 行
        cost = sum(d[r][r + 1] for r in range(19))
        min_c = cost
        for k in range(19):
            cost += d[k][k] - d[k][k + 1]
            if cost < min_c:
                min_c = cost
        if min_c < best_cost:
            best_cost, best_c = min_c, c
    return best_cost, best_c


def calc_diff20(dc: list[list[int]]) -> tuple[int, int]:
    """计算 20 行输入与标准字体一对一匹配时的最小差异及最优字符编号。"""
    best_cost, best_c = INF, 0
    for c in range(27):
        cost = sum(dc[c][r][r] for r in range(20))
        if cost < best_cost:
            best_cost, best_c = cost, c
    return best_cost, best_c


def calc_diff21(dc: list[list[int]]) -> tuple[int, int]:
    """计算 21 行输入与标准字体匹配时的最小差异及最优字符编号。"""
    best_cost, best_c = INF, 0
    for c in range(27):
        d = dc[c]
        # 重复第 k 行：第 k 行与第 k+1 行均对应标准第 k 行，取两者中差异较小者
        pref = [0] * 22
        for r in range(20):
            pref[r + 1] = pref[r] + d[r][r]
        suff = [0] * 22
        for r in range(20, 0, -1):
            suff[r] = suff[r + 1] + d[r][r - 1]
        min_c = min(pref[k] + min(d[k][k], d[k + 1][k]) + suff[k + 2] for k in range(20))
        if min_c < best_cost:
            best_cost, best_c = min_c, c
    return best_cost, best_c


def solve() -> None:
    data = iter(sys.stdin.read().split())
    try:
        f_cnt = int(next(data))
    except StopIteration:
        return

    font_raw = [next(data) for _ in range(f_cnt)]
    n = int(next(data))
    char_raw = [next(data) for _ in range(n)]

    # 将 20 位 01 串转换为整数，便于位运算计算汉明距离
    font = [[int(x, 2) for x in font_raw[c * 20 : (c + 1) * 20]] for c in range(27)]
    inp = [int(x, 2) for x in char_raw]

    # diff[i][c][r] 表示输入第 i 行与字符 c 的第 r 行的差异位变化数
    diff = [[[(inp[i] ^ font[c][r]).bit_count() for r in range(20)] for c in range(27)] for i in range(n)]

    # dp[i] 表示匹配完前 i 行的最小总修改代价
    dp = [INF] * (n + 1)
    prev = [(-1, '')] * (n + 1)
    dp[0] = 0

    for i in range(n):
        if dp[i] == INF:
            continue
        cur = dp[i]

        # 转移 1：当前字符占 19 行（缺失 1 行）
        if i + 19 <= n:
            dc = [[diff[i + r][c] for r in range(19)] for c in range(27)]
            cost, c = calc_diff19(dc)
            if cur + cost < dp[i + 19]:
                dp[i + 19] = cur + cost
                prev[i + 19] = (i, CHARS[c])

        # 转移 2：当前字符占 20 行（行数未变）
        if i + 20 <= n:
            dc = [[diff[i + r][c] for r in range(20)] for c in range(27)]
            cost, c = calc_diff20(dc)
            if cur + cost < dp[i + 20]:
                dp[i + 20] = cur + cost
                prev[i + 20] = (i, CHARS[c])

        # 转移 3：当前字符占 21 行（重复 1 行）
        if i + 21 <= n:
            dc = [[diff[i + r][c] for r in range(21)] for c in range(27)]
            cost, c = calc_diff21(dc)
            if cur + cost < dp[i + 21]:
                dp[i + 21] = cur + cost
                prev[i + 21] = (i, CHARS[c])

    # 回溯得到识别出的字符序列，首部多余的空白字符按数据规范剥离
    res = []
    curr = n
    while curr > 0:
        p, ch = prev[curr]
        res.append(ch)
        curr = p
    print("".join(reversed(res)).lstrip())


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 12:33
 * update_at: 2026-10-06 12:33
 */
#include <bits/stdc++.h>
typedef long long ll;

const ll MAXN = 1205;   // 输入行数上限（N < 1200）
const ll INF = 1e9;
const ll NUMC = 27;     // 字符集大小：空格 + 26 个小写字母

ll f_cnt;                                 // 字体文件行数（540）
ll n;                                     // 待识别图像的行数
ll font[NUMC][20];                        // font[c][r]：字符 c 的字模第 r 行压缩成的整数
ll inp[MAXN];                             // inp[i]：输入第 i 行压缩成的整数
ll diff[MAXN][NUMC][20];                  // diff[i][c][r]：输入第 i 行与字符 c 第 r 行的汉明距离
ll dp[MAXN];                              // dp[i]：匹配完前 i 行图像的最小总错误位代价
ll pre[MAXN];                             // pre[i]：dp[i] 的最优前驱状态
char ch[MAXN];                            // ch[i]：转移到状态 i 时识别出的字符
char ans[MAXN];                           // 回溯得到的结果串
ll ans_len;

char CHARS[NUMC + 1] = " abcdefghijklmnopqrstuvwxyz";

// 从字符串 s 读一个 20 位 01 串，压缩成整数
ll to_bits(char *s) {
    ll v = 0;
    for (ll i = 0; i < 20; ++i) {
        v = v * 2 + (s[i] - '0');
    }
    return v;
}

// 当前字符占 20 行：一一对应匹配，返回最优代价和字符编号
ll calc20(ll st, ll &best_c) {
    ll best = INF;
    for (ll c = 0; c < NUMC; ++c) {
        ll cost = 0;
        for (ll r = 0; r < 20; ++r) cost += diff[st + r][c][r];
        if (cost < best) {
            best = cost;
            best_c = c;
        }
    }
    return best;
}

// 当前字符占 19 行：枚举字模中被遗漏的行号 k，滑动增量更新求最小代价
ll calc19(ll st, ll &best_c) {
    ll best = INF;
    for (ll c = 0; c < NUMC; ++c) {
        // 初始 k=0：输入前 19 行对应字模第 1..19 行
        ll cost = 0;
        for (ll r = 0; r < 19; ++r) cost += diff[st + r][c][r + 1];
        ll min_c = cost;
        // k 从 0 增到 18：输入第 k 行改为对应字模第 k 行（原来对应第 k+1 行）
        for (ll k = 0; k < 19; ++k) {
            cost += diff[st + k][c][k] - diff[st + k][c][k + 1];
            if (cost < min_c) min_c = cost;
        }
        if (min_c < best) {
            best = min_c;
            best_c = c;
        }
    }
    return best;
}

// 当前字符占 21 行：枚举字模中被复制的行号 k，用前后缀和 O(1) 求每种 k 的代价
ll calc21(ll st, ll &best_c) {
    ll best = INF;
    for (ll c = 0; c < NUMC; ++c) {
        ll pref[22], suff[22];
        // pref[k] = 输入前 k 行与字模前 k 行的差异和
        pref[0] = 0;
        for (ll r = 0; r < 20; ++r) pref[r + 1] = pref[r] + diff[st + r][c][r];
        // suff[k] = 输入第 k..20 行与字模第 k-1..19 行的差异和
        suff[21] = 0;
        for (ll r = 20; r >= 1; --r) suff[r] = suff[r + 1] + diff[st + r][c][r - 1];
        ll min_c = INF;
        for (ll k = 0; k < 20; ++k) {
            // 第 k、k+1 行都来自字模第 k 行，只算损坏较小的一行
            ll cost = pref[k] + std::min(diff[st + k][c][k], diff[st + k + 1][c][k]) + suff[k + 2];
            if (cost < min_c) min_c = cost;
        }
        if (min_c < best) {
            best = min_c;
            best_c = c;
        }
    }
    return best;
}

void solve() {
    std::cin >> f_cnt;
    static char s[64];
    for (ll i = 0; i < f_cnt; ++i) {
        std::cin >> s;
        // 字体共 541 行 = 1 行 N + 540 行图案，每 20 行是一个字符的字模
        if (i < NUMC * 20) font[i / 20][i % 20] = to_bits(s);
    }
    std::cin >> n;
    for (ll i = 0; i < n; ++i) {
        std::cin >> s;
        inp[i] = to_bits(s);
    }

    // 预处理每行与每个字模行的汉明距离：异或后数 1 的个数
    for (ll i = 0; i < n; ++i) {
        for (ll c = 0; c < NUMC; ++c) {
            for (ll r = 0; r < 20; ++r) {
                diff[i][c][r] = __builtin_popcountll(inp[i] ^ font[c][r]);
            }
        }
    }

    // 线性划分 DP：dp[i] 由 dp[i-19]、dp[i-20]、dp[i-21] 转移而来
    for (ll i = 1; i <= n; ++i) dp[i] = INF;
    dp[0] = 0;
    for (ll i = 0; i < n; ++i) {
        if (dp[i] >= INF) continue;
        ll c;
        if (i + 19 <= n) {
            ll cost = calc19(i, c);
            if (dp[i] + cost < dp[i + 19]) {
                dp[i + 19] = dp[i] + cost;
                pre[i + 19] = i;
                ch[i + 19] = CHARS[c];
            }
        }
        if (i + 20 <= n) {
            ll cost = calc20(i, c);
            if (dp[i] + cost < dp[i + 20]) {
                dp[i + 20] = dp[i] + cost;
                pre[i + 20] = i;
                ch[i + 20] = CHARS[c];
            }
        }
        if (i + 21 <= n) {
            ll cost = calc21(i, c);
            if (dp[i] + cost < dp[i + 21]) {
                dp[i + 21] = dp[i] + cost;
                pre[i + 21] = i;
                ch[i + 21] = CHARS[c];
            }
        }
    }

    // 从 n 逆序回溯，再把首部多余空格剥离后正序输出
    ll rev_len = 0;
    static char rev[MAXN];
    for (ll i = n; i > 0; i = pre[i]) {
        rev[rev_len++] = ch[i];
    }
    // ans[st..ans_len-1] 为正序文本，st 跳过开头的空格字符
    ll ans_len = 0;
    for (ll i = rev_len - 1; i >= 0; --i) ans[ans_len++] = rev[i];
    ll st = 0;
    while (st < ans_len - 1 && ans[st] == ' ') ++st;
    for (ll i = ans_len - 1; i >= st; --i) std::cout << ans[i];
    std::cout << std::endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    solve();
    return 0;
}

复杂度

时间复杂度：
- 预处理行汉明距离：输入共 $N$ 行，字符集大小 $|\Sigma| = 27$ ，字模高度 $H = 20$ 。每次位运算耗时 $O(1)$ ，预处理耗时 $O(N \cdot |\Sigma| \cdot H)$ 。
- DP 转移：状态数为 $N$ ，每个状态枚举 3 种步长以及 27 个字符，每种形态的最小代价计算均为 $O(H)$ ，转移耗时 $O(N \cdot |\Sigma| \cdot H)$ 。
- 总时间复杂度为 $O(N \cdot |\Sigma| \cdot H)$ 。当 $N \le 1200$ 时，总操作次数约为 $1.9 \times 10^6$ ，在 Python 3 环境下仅需约 $0.2\,\text{s}$ 。
空间复杂度：
- 保存预处理距离数组和 DP 状态记录需要 $O(N \cdot |\Sigma| \cdot H)$ 的空间，实测内存占用不超过 $25\,\text{MB}$ 。

总结

结构化特征提取：利用位运算与整数压缩，在常数时间内求出 20 位行间的汉明距离，极大地削减了字符比对的常数。
局部对齐优化：对于长度为 19 和 21 的变长匹配，通过滑动更新和前后缀和，将单字符各可能受损位置的枚举优化至 $O(H)$ ，使整体 DP 复杂度达到最优阶。

图示解析

flowchart LR
    A["dp[i-21]: 匹配重复行字符 (L=21)"] -->|"min_cost21"| D["dp[i]"]
    B["dp[i-20]: 匹配正常字符 (L=20)"] -->|"min_cost20"| D
    C["dp[i-19]: 匹配缺失行字符 (L=19)"] -->|"min_cost19"| D

题目描述

这个问题需要你写一个程序完成字符识别的任务. 每个完整的字符图案有 20 行,20 位.每个位是“0”或“1”.图 1a 对应着输入文件中的符号图案. 文件 font.in 包括了 27 个字符图案的信息,以这样的顺序记录:

text

1_abcdefghijklmnopqrstuvwxyz

其中 _ 表示空格字符.每个完整字符长 20 行.

输入文件包含一个或多个可能损坏的字符图案.一个字符图案可能以这些方式被损坏.

最多有一行被可能被复制了（就接在原来那一行的下面）最多有一行可能丢失了有些“0”可能被改成“1” 有些“1”可能被改成“0”

不会有任何一个字符图案既多余了一行并且又丢失了一行.在测试数据的任何一个字符图案中,“0”和“1”的被改变率不超过 30%. 被复制的那一行中,原来的行和多余的行可能都损坏了,而且损坏的部分可能并不相同. 写一个程序,使用 font.in 提供的字体,在输入文件提供的图象中识别出一个或多个的字符序列. 使用提供的字体图象来识别字符的时候,要找出最佳的多余行或遗漏行,使找出的所有“0”和 “1”的变化数量最小.在所有可能的多余行中,只按损坏数据最少的那一行计算.你必须确定和输入序列最接近的字符序列（就是损坏数据最少的那一个）.每个测试数据有唯一的最优解.正确的解答必须使用到输入文件中的所有数据.

INPUT FORMAT (both input files)

两个输入文件都以一个整数 N 开始（19 < N < 1200）,表示接下去的行数. N

(位 1)(位 2)(位 3) … (位 20)
(位 1)(位 2)(位 3) … (位 20)
…

每行有 20 位的宽度.在0和1 之间没有空格分开.

文件 font.in 描述字体.它总有 541 行.它在每个测试数据中可能不同.

SAMPLE INPUT (file char.in)

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47例:font.in 的开头（不完全的）,  例 :char.in 显示了一个损坏的
有“空格”和“a”                   “a” 

font.in                           char.in 
--------------                  ------------------
540                             19
00000000000000000000            00000000000000000000
00000000000000000000            00000000000000000000
00000000000000000000            00000000000000000000
00000000000000000000            00000011100000000000
00000000000000000000            00100111011011000000
00000000000000000000            00001111111001100000
00000000000000000000            00001110001100100000
00000000000000000000            00001100001100010000
00000000000000000000            00001100000100010000
00000000000000000000            00000100000100010000
00000000000000000000            00000010000000110000
00000000000000000000            00001111011111110000
00000000000000000000            00001111111111110000
00000000000000000000            00001111111111000000
00000000000000000000            00001000010000000000
00000000000000000000            00000000000000000000
00000000000000000000            00000000000001000000
00000000000000000000            00000000000000000000
00000000000000000000            00000000000000000000 
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000011100000000000 
00000111111011000000
00001111111001100000
00001110001100100000
00001100001100010000
00001100000100010000
00000100000100010000
00000010000000110000
00000001000001110000
00001111111111110000
00001111111111110000
00001111111111000000
00001000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000

OUTPUT FORMAT

你的程序必须建立一个输出文件,包含一个识别出来的字符串.它的格式是一个单行的 ASCII 文本.

输出文件中不应该包含任何分隔符.如果你的程序没有识别出一个特定的字符,就必须在适当的位置输出一个“?”.

SAMPLE OUTPUT (file char.out)

text

1a

注意,上面输出的一行是两个字符:“a”后面还跟着一个空格.（这是按原文译的,其实我也不理解这句话,应该只有一个字符“a”吧——译者注）

字符识别

目录

形式化题目

正解

思路

1. 状态定义

2. 行间汉明距离预处理

3. 三种长度的匹配代价计算

4. 路径回溯

代码

复杂度

总结

图示解析