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

 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

正解trie树，然而hash时间够，水过。

注意dp要全部附零。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ull unsigned long long
#define seed 13131
struct node
{
    int cnt;
    ull hs[25];
    void push(ull h){hs[++cnt] = h;}
}p[15];
int n,m;
char s[15],a[2000050];
int dp[2000050];
ull has[2000050],k0[2000050];
void make_has()
{
    int len = strlen(a+1);
    for(int i=1;i<=len;i++)
        has[i]=seed*has[i-1]+a[i],dp[i]=0;
}
ull get_hs(int l,int r)
{
    return has[r]-has[l-1]*k0[r-l+1];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        int len = strlen(s+1);
        ull h = 0;
        for(int j=1;j<=len;j++)
            h = seed*h+s[j];
        p[len].push(h);
    }
    k0[0] = 1;
    for(int i=1;i<=2000020;i++)
        k0[i]=k0[i-1]*seed;
    for(int i=1;i<=m;i++)
    {
        scanf("%s",a+1);
        make_has();
        int len = strlen(a+1);
        dp[len+1]=0;
        for(int j=len;j>=1;j--)
        {
            for(int l=1;l<=10&&j+l-1<=len;l++)
            {
                ull h = get_hs(j,j+l-1);
                for(int w=1;w<=p[l].cnt;w++)
                {
                    if(h==p[l].hs[w])
                    {
                        dp[j]=max(dp[j],dp[j+l]+l);
                        break;
                    }
                }
            }
        }
        printf("%d
",dp[1]);
    }
    return 0;
}