Luogu P2292 [HNOI2004]L语言

题目链接 \(Click\) \(Here\)

好久没写\(DP\)了真是水平下降不少，一眼把这个题搞成贪心了，然后一发交上只有\(37\)分\(QwQ\)

这个题好像还可以\(AC\)自动机胡搞？不过这里\(DP\)就已经很简洁易懂易想了。对每一个已经完成完整前缀匹配的点，它可以向更深的地方去找，也可以跳回原点去进行下一个词的匹配。为了避免出现指数级别的计算，跳回原点后就不再考虑分支的可能，而是一路向下找，只要找到有一个可用的情况就记录即可。

#include <bits/stdc++.h>
using namespace std;

char s[1048577];
int n, m, tag[210];
int max_size, ch[210][30];

void add_str () {
    int l = strlen (s), now = 0;
    for (int i = 0; i < l; ++i) {
        if (!ch[now][s[i] - 'a']) {
            ch[now][s[i] - 'a'] = ++max_size;
        }
        now = ch[now][s[i] - 'a'];
    }
    tag[now] = true; //结束标志
}

int match[1048577];

int get_ans () {
    int l = strlen (s), now = 0;
    memset (match, 0, sizeof (match));
    match[0] = true;
    for (int i = 0; i < l; ++i) {
        if (match[i]) {
            //match[i]代表前i位的前缀可用
            //从i + 1位 (字符串第i位) 回溯原点去找
            int pos = 0, t = i;
            while (ch[pos][s[t] - 'a'] && t < l) {
                pos = ch[pos][s[t] - 'a'];
                if (tag[pos] == true) {
                    //结束标记
                    match[t + 1] = true;
                }
                ++t;
            }
        }
    }
    for (int i = l; i >= 0; --i) {
        if (match[i]) return i;
    }
}

int main () {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        scanf ("%s", s);
        add_str ();
    }
    for (int i = 1; i <= m; ++i) {
        scanf ("%s", s);
        cout << get_ans () << endl;
    }
} 

Luogu P2292 [HNOI2004]L语言

原文：https://www.cnblogs.com/maomao9173/p/10441536.html