字典树 get！

· · 个人记录

关于字典树

一种支持字符串查找、查询前缀出现次数的树形结构，详见这里

这里总结一下建树的两种方式：

1.静态树：

相当于一棵 26 叉树，用桶存每个节点的 26 个字母，如果出现过就打上 DFS 序，再开一个 vis 数组记录单词结束为止的 DFS 序。

优点：

快的一批，比哈希快到不知哪里去了~

缺点：

空间复杂度高，因为每个节点会有好多字母用不到，浪费大量空间。

2.动态开点：

这就是个链式前向星，遇到一个节点，发现没有该字母的话，就现场连边，单词为边权，单词结束标记打在点上。

优点：

节省了大量空间，而且比哈希快。

缺点：

自带大常数，因为要判断在节点上没有该字母，需要 O(26) 跑一遍（最坏情况下）

模板：

codevs \ \ 4189

传送门

又翻到隔壁 codevs 去扒了道题做。。。

这个真的是一道模板了，也没有什么好说的了。。。

不过值得注意的是，这道题的数据范围应该开到 300005 ，蜜汁数据

#define ASC c[i]-'a'
int n,m,tot;
char c[10];
int trie[MAXN][26];
int vis[MAXN];

void insert()
{
    int u = 0;
    for(int i=1;c[i];i++)
    {
        if(!trie[u][ASC])
            trie[u][ASC] = ++tot;
        u = trie[u][ASC];
    }
    vis[u] = 1;
}
bool find()
{
    int u = 0;
    for(int i=1;c[i];i++)
    {
        if(!trie[u][ASC]) return 0;
        u = trie[u][ASC];
    }
    return 1;
}
int main(void)
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> (c+1);
        insert();
    }
    cin >> m;
    for(int i=1;i<=m;i++)
    {
        cin >> (c+1);
        if(find())  puts("YES");
        else        puts("NO" );
    }
    return 0;
}

DP：

传送门

一开始打算暴搜所有状态的，后来想了想这样太蠢了，还是 DP 吧。。。

字典树查前缀就不说了。

那么为什么需要 DP 呢？如下：

3 1

ab

abc

cc

adccc

这样的话，正解显然是 5 ，但由于 ab 和 abc 有部分重复，所以直接找的话答案就变成了 4 因为当字典树找到 ab 时就会返回，不会去找 abc 了。

所以要用 DP ，记 f[i] 表示从 1 到 i 位能不能理解。

其实个人感觉这并不是标准的 DP ，只是暴力的把所有可能的情况 n^2 枚举一遍。。。 

int n,m,tot=1;
char c[20000000];
int trie[MAXN][30];
int f[MAXN];
int vis[MAXN];

void insert()
{
    int u = 1;
    for(int i=1;c[i];i++)
    {
        if(!trie[u][ASC])
            trie[u][ASC] = ++tot;
        u = trie[u][ASC];
    }
    vis[u] = 1;
}

int find()
{
    int ans,u;
    int len = strlen(c+1);
    for(int j=0;j<=len;j++)
    {
        if(f[j] != j) continue;
        u = 1;
        ans = j;
        for(int i=j+1;c[i];i++)
        {
            if(!trie[u][ASC]) break;
            if(vis[trie[u][ASC]])   f[i] = i;
            u = trie[u][ASC];
        }
    }
    return ans;
}

int main(void)
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        cin >> (c+1);
        insert();
    }
    for(int i=1;i<=m;i++)
    {
        memset(f,0,sizeof f);
        cin >> (c+1);
        f[0] = 0;
        cout << find() << endl;
    }
    return 0;
}