L 语言

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1826 字
Trie 加可达性 DP 求最长可理解前缀
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1475
// 题意：给 n 个字典单词和 m 段文章，对每段文章求能被切分成字典单词序列的最长前缀的长度。
// 思路：单词建 Trie，对文章做可达性 DP：dp[i] 表示前 i 个字符可被理解，从每个 dp[i] 为真的位置沿 Trie 往下走，遇到单词结尾就置 dp[j+1] 为真，取最大的真位置即为答案。
// 复杂度：O(文章长度 × 最长单词长度) 时间 / O(字典总长度 + 文章长度) 空间
// 易错点：从 dp[i] 往下走时最多只走「最长单词长度」步就停，否则长文章会退化成 O(L^2)。
// 易错点：答案是「最长可理解前缀的位置」，不是「是否能整段理解」，要取最后一个 dp 为真的下标。
#include <bits/stdc++.h>
using namespace std;
struct Node {
    int ch[26];
    bool ed;
    Node(){
        memset(ch, 0, sizeof(ch));
        ed = false;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if(!(cin >> n >> m)) return 0;
    vector<Node> tr;
    tr.push_back(Node());
    int maxLen = 0;
    for(int i = 0; i < n; i++){
        string w;
        cin >> w;
        if((int)w.size() > maxLen) maxLen = (int)w.size();
        int u = 0;
        for(int j = 0; j < (int)w.size(); j++){
            int c = w[j] - 'a';
            if(!tr[u].ch[c]){
                tr[u].ch[c] = (int)tr.size();
                tr.push_back(Node());
            }
            u = tr[u].ch[c];
        }
        tr[u].ed = true;
    }
    for(int i = 0; i < m; i++){
        string s;
        cin >> s;
        int L = (int)s.size();
        vector<char> dp(L + 1, 0);
        dp[0] = 1;
        for(int j = 0; j < L; j++){
            if(!dp[j]) continue;
            int u = 0;
            int lim = min(L, j + maxLen);
            for(int k = j; k < lim; k++){
                int c = s[k] - 'a';
                if(!tr[u].ch[c]) break;
                u = tr[u].ch[c];
                if(tr[u].ed) dp[k + 1] = 1;
            }
        }
        int ans = 0;
        for(int j = L; j >= 0; j--){
            if(dp[j]){
                ans = j;
                break;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}
L 语言

正文

一本通·提高篇的其它内容
