[IOI 1996 / USACO2.3] 最长前缀 Longest Prefix

题意

给定最多 200 个短原串，它们可以重复使用。求目标序列能由这些原串拼出的最长前缀长度。

思路

令 reachable[i] 表示长度为 i 的前缀可以拼出。若 i 可达，检查从 i 开始的子串是否属于某种原串；匹配长度为 length 时令 reachable[i+length]=1。

原串长度最多 10。先按长度分成集合后，每个可达位置最多只做 10 次切片和集合查询，而不是遍历 200 个原串。

Python 知识

tokens.index(b".") 找到原串区与目标串的分隔符。
defaultdict(set) 同时完成按长度分组和去重。
b"".join(...) 拼回跨多行输入的目标序列。
bytearray(n+1) 是紧凑的布尔 DP 数组。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23import sys
from collections import defaultdict


tokens = sys.stdin.buffer.read().split()
separator = tokens.index(b".")
primitives_by_length = defaultdict(set)
for primitive in tokens[:separator]:
    primitives_by_length[len(primitive)].add(primitive)
sequence = b"".join(tokens[separator + 1:])

reachable = bytearray(len(sequence) + 1)
reachable[0] = 1
answer = 0
for start in range(len(sequence)):
    if not reachable[start]:
        continue
    for length, primitives in primitives_by_length.items():
        end = start + length
        if sequence[start:end] in primitives:
            reachable[end] = 1
            answer = max(answer, end)
print(answer)

复杂度

最多 10 种长度，时间 $O(10|S|)$ 加短字符串哈希成本，空间 $O(|S|+|P|)$ 。

总结

“按长度分组为集合”是 Python 处理许多短模式串时很实用的优化。

[IOI 1996 / USACO2.3] 最长前缀 Longest Prefix

目录

题意

思路

Python 知识

代码

复杂度

总结