发布于 由itewqq

[训练指南][字典树] 使用前缀关系进行递推 字典树加速 LA 3942

题意给一个字符串和单词字典，问把字符串分割成词典中存在的单词可以有多少种方法（单词可以重复使用）首先是像dp那样考虑，令d(i)为从第i个字符开始到结束的字符串的方案数，然后可以得出d(i)=sum{d(i+len(x))|单词x是S[i,l]的前缀}。然后就是找一个串有多少个单词前缀了。。。字典树搜索即可搞定，就是在Trie中查找S[i,l]，一路查过去把遇到的是单词节点的地方加上那里的d就可以了。

很蠢地空间开小了wa。。。很蠢地每次都对后缀求了strlen导致2000+ms惨案。。。很蠢地忘记了取模。。。

#include 
#include 
#include 
#include
#include
#include
#include
#include
#include
//#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn=3e5+5;
const int MOD=20071027;
const int maxnode=4000*100+5;
const int csize=27;

char st[maxn];
int d[maxn];
int n;

int ch[maxnode][csize];
int val[maxnode];
int sz;
int idx(char c)
{
    return c-'a';
}

void clear()
{
    sz=1;
    memset(ch[0],0,sizeof(ch[0]));
}

void insert(char *s)
{
    int u=0,n=strlen(s);
    for (int i=0; i=0; i--)
        {
            search(st+i,d[i],i);
        }
        printf("Case %d: %d\n",cnt,d[0]%MOD);
    }
    return 0;
}

 

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

此站点使用 Akismet 来减少垃圾评论。了解我们如何处理您的评论数据。