P2292 [HNOI2004]L语言

题目描述
标点符号的出现晚于文字的出现，所以以前的语言都是没有标点的。现在你要处理的就是一段没有标点的文章。

一段文章T是由若干小写字母构成。一个单词W也是由若干小写字母构成。一个字典D是若干个单词的集合。我们称一段文章T在某个字典D下是可以被理解的，是指如果文章T可以被分成若干部分，且每一个部分都是字典D中的单词。

例如字典D中包括单词{‘is’, ‘name’, ‘what’, ‘your’}，则文章‘whatisyourname’是在字典D下可以被理解的，因为它可以分成4个单词：‘what’, ‘is’, ‘your’, ‘name’，且每个单词都属于字典D，而文章‘whatisyouname’在字典D下不能被理解，但可以在字典D’=D+{‘you’}下被理解。这段文章的一个前缀‘whatis’，也可以在字典D下被理解，而且是在字典D下能够被理解的最长的前缀。

给定一个字典D，你的程序需要判断若干段文章在字典D下是否能够被理解。并给出其在字典D下能够被理解的最长前缀的位置。

输入输出格式
输入格式：
输入文件第一行是两个正整数n和m，表示字典D中有n个单词，且有m段文章需要被处理。之后的n行每行描述一个单词，再之后的m行每行描述一段文章。

其中1<=n, m<=20，每个单词长度不超过10，每段文章长度不超过1M。

输出格式：
对于输入的每一段文章，你需要输出这段文章在字典D可以被理解的最长前缀的位置。

这题卡了一年了今天提到 \(trie\) 树回来 \(A\) 掉

这题的精髓其实是 读题 ：每个单词长度不超过 10 个字母 什么意思呢， 意思就是判断当前位置结尾的单词是否合法， 只需向前枚举最多 \(10\) 个字母看是否有单词能匹配即可， 是不是很暴力？

然而这还不全面， 万一有这个单词了， 可这个单词的上一个位置， 他的前驱不能匹配怎么办？ 我们用一个数组记录以当前位置结尾是否能够匹配， 判断下一个子段的时候判断一下。比如枚举到的区间为 \([L,R]\) 当 \(L - 1\) 合法时才判断 \([L,R]\) 是否是一个单词。

这一个状态是否合法的先决因素是上一个末尾是否合法， 是不是有点 \(dp\) 的味道？

其实我觉得也算不上 \(dp\) 啦，嗯， 一个很暴力的 \(dp\)

判断子段是否为合法单词用 \(trie\) 树即可

Code

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
int RD(){
    int flag = 1, out = 0;char c = getchar();
    while(c < '0' || c > '9'){if(c == '-')flag = -1;c = getchar();}
    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
    return flag * out;
    }
const int maxn = 1000019;
int numm, nump;
int trie[maxn][26], tot;
int end[maxn];
char mat[maxn];
void insert(char s[]){
    int len = strlen(s), now = 0;
    for(int i = 0;i < len;i++){
        int id = s[i] - 'a';
        if(!trie[now][id])trie[now][id] = ++tot;
        now = trie[now][id];
        }
    end[now] = 1;
    }
bool find(int l, int r){
    int now = 0;
    for(int i = l;i <= r;i++){
        int id = mat[i] - 'a';
        if(!trie[now][id])return 0;
        now = trie[now][id];
        }
    if(end[now])return 1;
    }
bool dp[maxn];
int main(){
    numm = RD(); nump = RD();
    for(int i = 1;i <= numm;i++){
        cin>>mat;
        insert(mat);
        }
    while(nump--){
        cin>>mat;int len = strlen(mat);
        memset(dp, 0, sizeof(dp));
        for(int i = 0;i < len;i++){
            for(int j = 0;j <= 10;j++){
                int l = i - j;
                if(l < 0)continue;
                if(l == 0)dp[i] = find(l, i);//这里分一下情况， 由于开始位置为0，-1这个位置其实是dp的边界，是合法的，但是数组没有负数下标
                else{
                    if(!dp[l - 1])continue;
                    dp[i] = find(l ,i);
                    }
                if(dp[i])break;
                }
            }
        int ans = 0;
        for(int i = len - 1;i >= 0;i--){
            if(dp[i]){
                ans = i + 1;
                break;
                }
            }
        printf("%d\n", ans);
        }
    return 0;
    }

P2292 [HNOI2004]L语言

原文：https://www.cnblogs.com/Tony-Double-Sky/p/9330728.html