最长前缀

形式化题目

给定一个字符串集合 $P = \{p_1, p_2, \dots, p_m\}$ ，其中每个元素的长度满足 $1 \le |p_j| \le 10$ 。同时给定一个长字符串 $S$ （ $|S| \le 200,000$ ）。

定义一个字符串可分解，当且仅当它可以表示为集合 $P$ 中若干元素的串联（元素可重复使用）。求最大的整数 $K \in [0, |S|]$ ，使得前缀子串 $S[0:K]$ 可以由 $P$ 中的元素分解。

样例解释与图示

以样例为例：

基本元素集合 $P = \{\text{"A"}, \text{"AB"}, \text{"BA"}, \text{"CA"}, \text{"BBC"}\}$
目标字符串 $S = \text{"ABABACABAABC"}$ （长度为 12）

我们观察前缀的分解过程：

长度 0：空串，显然可分解。
长度 1："A"，匹配元素 "A"，可分解。
长度 2："AB"，匹配元素 "AB"，可分解。
长度 3："ABA"，由 "AB" + "A" 拼接，可分解。
长度 4："ABAB"，由 "AB" + "AB" 拼接，可分解。
长度 5："ABABA"，由 "ABAB" + "A" 拼接，可分解。
长度 6："ABABAC"，末尾两字符为 "AC"，不在集合中；末尾单字符 "C" 也不在集合中。此时前缀 6 不可由前缀 5 或 4 拼接得出。
长度 7："ABABACA"，由可分解的前缀 5（"ABABA"）+ "CA" 拼接，因此前缀 7 可分解！
…以此类推，最终前缀 11 为 "ABABACABAAB"，可分解；而前缀 12 "ABABACABAABC" 无法被分解。

因此最长前缀长度为 $11$ 。

flowchart LR
    S0["dp[0]=True<br/>(空串)"] -->|"AB"| S2["dp[2]=True<br/>'AB'"]
    S0 -->|"A"| S1["dp[1]=True<br/>'A'"]
    S1 -->|"BA"| S3["dp[3]=True<br/>'ABA'"]
    S2 -->|"AB"| S4["dp[4]=True<br/>'ABAB'"]
    S4 -->|"A"| S5["dp[5]=True<br/>'ABABA'"]
    S5 -->|"CA"| S7["dp[7]=True<br/>'ABABACA'"]
    S7 -->|"BA"| S9["dp[9]=True<br/>...ABACA"]
    S9 -->|"AB"| S11["dp[11]=True<br/>(最长=11)"]

思路

1. 朴素方法与状态定义

如果采用回溯搜索（DFS），从前缀 0 开始尝试枚举每一个集合元素进行拼接，在包含重复前后缀字符的序列中会产生大量重复分支，时间复杂度在最坏情况下为指数级，会超时。

注意到当前前缀 $S[:i]$ 是否能被拼接，仅取决于是否存在一个分割点 $i-L$ ，满足：

前缀 $S[:i-L]$ 本身是可分解的；
剩余的后缀子串 $S[i-L:i]$ 属于集合 $P$ 。

这具备显然的最优子结构与无后效性，因此可以使用动态规划求解。

定义布尔数组 $dp[i]$ 表示前缀 $S[0:i]$ （长度为 $i$ ）是否可以由集合 $P$ 拼接而成。

初始状态： $dp[0] = \text{True}$ （空串由 0 个元素拼接而成）。

2. 优化状态转移

集合中每个元素的长度非常短（ $1 \le |p| \le 10$ ）。这意味着转移步长 $L$ 只能在 $1$ 到 $10$ 之间取值。

我们将集合 $P$ 中的元素按长度分组存入哈希集合 by_len[L]。对于前缀长度 $i$ 从 $1$ 到 $|S|$ ：

枚举可能存在的元素长度 $L \in \text{lens}$ 且 $L \le i$ ；
优先检查 $dp[i-L]$ 是否为 $\text{True}$ 。若为 $\text{False}$ 则无需进行子串截取与集合查询；
若 $dp[i-L] = \text{True}$ 且子串 $S[i-L:i] \in \text{by\_len}[L]$ ，则说明 $dp[i] = \text{True}$ 。
一旦 $dp[i]$ 被置为 $\text{True}$ ，更新最远长度记录 $ans = i$ ，并直接 break 结束内层枚举。

代码

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#!/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-10-01 03:45
# update_at: 2026-10-01 03:45

import sys


def find_max_prefix(primitives: list[str], s: str) -> int:
    """计算字符串 s 能由基本元素集合拼出的最长前缀长度。"""
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    ans = 0

    # 按元素长度分组，便于快速向前匹配
    by_len: dict[int, set[str]] = {}
    for p in primitives:
        by_len.setdefault(len(p), set()).add(p)

    lens = sorted(by_len.keys())

    for i in range(1, n + 1):
        for l in lens:
            if l > i:
                break
            if dp[i - l] and s[i - l:i] in by_len[l]:
                dp[i] = True
                ans = i
                break

    return ans


def solve() -> None:
    # 元素集合与长字符串 S 都可能跨多行，所以只按空白切 token，靠「单独一个 '.' token」分界
    data = iter(sys.stdin.buffer.read().split())

    first = next(data, None)                     # 空输入：沿用原来的 if not tokens 守卫
    if first is None:
        return

    # 不靠下标：'.' 之前的 token 依次是集合元素，之后剩下的 token 拼成长字符串 S
    primitives: list[str] = []
    token = first
    while token != b".":
        primitives.append(token.decode())
        token = next(data)                       # 题面保证有 '.'，缺分界符属非法输入
    s = "".join(token.decode() for token in data)

    ans = find_max_prefix(primitives, s)
    print(ans)


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/**
 * 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 09:17
 * update_at: 2026-10-06 09:17
 */

// 最长前缀：布尔线性 DP，dp[i] 表示前缀 S[0:i] 能否由集合 P 拼出。
// 元素长度不超过 10，所以转移只需向前看 1..10 个字符；
// 用 set<string> 按长度存集合元素，转移时做一次子串查询。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <string>
#include <vector>

typedef long long ll;

using namespace std;

const int MAXL = 11; // 元素长度最大为 10，转移步长只取 1..10

string s;                        // 拼接后的长序列 S
bool dp[200005];                 // dp[i]：前缀长度 i 是否可分解，下标即状态
set<string> by_len[MAXL];        // by_len[L]：长度为 L 的所有元素，按长度分组
vector<ll> lens;                 // 出现过的元素长度，从小到大（已排序，方便 break）

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // 元素集合与 S 都可能跨多行，直接按空白切 token 读，
    // 读到单独一个 "." 就说明集合结束，其后所有 token 拼成 S
    string token;
    bool seen_dot = false;
    while (cin >> token) {
        if (!seen_dot) {
            if (token == ".") {
                seen_dot = true;
            } else {
                ll l = token.size();
                if (by_len[l].empty()) lens.push_back(l); // 记录出现过的长度
                by_len[l].insert(token);
            }
        } else {
            s += token; // S 跨多行，换行符不是 S 的一部分
        }
    }
    sort(lens.begin(), lens.end()); // lens 必须有序，转移时才能 l > i 就 break

    ll n = s.size();
    dp[0] = true; // 空串可分解
    ll ans = 0;

    for (ll i = 1; i <= n; i++) {
        // 枚举最后一段元素的长度 L，只有 dp[i-L] 为真才值得查子串
        for (ll j = 0; j < (ll)lens.size(); j++) {
            ll l = lens[j];
            if (l > i) break;          // lens 有序，后面更长，直接停
            if (!dp[i - l]) continue;
            // S 的下标从 0 开始：末段是 S[i-l .. i-1]
            if (by_len[l].count(s.substr(i - l, l))) {
                dp[i] = true;
                ans = i;               // 命中即更新答案，跳出内层
                break;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

复杂度分析

时间复杂度：预处理集合元素耗时 $O(\sum |p|) \le O(200 \times 10) = O(2000)$ ；DP 外层循环运行 $|S|$ 次，内层至多遍历 $10$ 个不同的长度并做一次 $O(L)$ 的哈希查找，总时间复杂度为 $O(10 \cdot |S|)$ 。对于 $|S| \le 200,000$ ，操作次数约 $2 \times 10^6$ ，在 Python 3 中仅需约 0.03 秒。
空间复杂度：存储字符串 $S$ 与 DP 数组占用 $O(|S|)$ 空间，集合存储占用常数空间，空间复杂度为 $O(|S|)$ 。

总结

本题利用了“基本元素长度极短（ $\le 10$ ）”这一关键约束，将字符串匹配问题转化为有限步长的布尔型线性 DP。在状态转移时通过“优先判定前驱状态合法性”以及“命中即 break”进行剪枝，使算法运行效率极高。

目录

形式化题目

样例解释与图示

思路

1. 朴素方法与状态定义

2. 优化状态转移

代码

复杂度分析

总结