『Trie树·DP』 [HNOI2004]L语言

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$

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

一段文章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下能够被理解的最长前缀的位置。

$\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$

第一次写这种题直接一发暴力70分…居然要用DP来维护。

我们对于这些字符串的匹配问题肯定要建立trie树。

我们设$f[i]$表示前缀$[1,i]$是否已经完成了匹配，当$f[i]=1$时，若$[i+1,j]$也被匹配则$f[j]=1$.表示$j$也已经被匹配。

至于如何匹配我们可以使用trie树来进行维护。这样问题就很简单了。

$\mathrm{C}\mathrm{o}\mathrm{d}\mathrm{e}$

#include <cstdio>
#include <string.h>
#include <iostream> using namespace std;
const int N = 300;
const int M = 5e6;int n, m;
int cnt = 1;
int trie[N*N][30], end[N*N], f[M];
char s[M];void insert(void)
{
    cin>>s+1;int len = strlen(s+1), p = 1;for (int i=1;i<=len;++i){
    if (!trie[p][s[i]-'a']) trie[p][s[i]-'a'] = ++ cnt;p = trie[p][s[i]-'a'];}end[p] ++;return;
} void query(void)
{
    cin>>s+1;int len = strlen(s+1), ans;memset(f,0,sizeof f);f[0] = 1;for (int i=0;i<=len;++i) {
    if (f[i] == 0) continue;else ans = i;for (int j=i+1,p=1;j<=len;++j){
    if (!trie[p][s[j]-'a']) break;p = trie[p][s[j]-'a'];if (end[p] >= 1) f[j] = 1;}}cout<<ans<<endl;
}int main(void)
{
    freopen("language.in","r",stdin);freopen("language.out","w",stdout);cin>>n>>m;for (int i=1;i<=n;++i) insert();for (int i=1;i<=m;++i) query();return 0;
}