首页 > 代码库 > LA 3942 Remember the Word (Trie)

LA 3942 Remember the Word (Trie)

2024-07-17 06:00:36   223人阅读

Remember the Word

题目：链接

题意：给出一个有S个不同单词组成的字典和一个长字符串。把这个字符串分解成若干个单词的连接（单词可以重复使用），有多少种方法？

思路：令d[i]表示从字符i开始的字符串（后缀s[i..L]）的分解数，这d[i] = sum{d(i+len(x)) | 单词x是其前缀}。然后将所有单词建成一个Trie树，就可以将搜索单词的复杂度降低。

代码：
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<fstream>
#include<cstring>
#include<ctype.h>
#include<iostream>
#include<algorithm>
#define INF (1<<30)
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i, n) for (int i = 0; i < n; i++)
#define debug puts("===============")
typedef long long ll;
using namespace std;
const int maxnode = 400010, charset = 26;
int d[300100] = {0}, len;
const int mod = 20071027;
struct Trie {
    int ch[maxnode][charset];
    int val[maxnode];
    int sz;
    void init() {
        sz = 1;
        memset(ch[0], 0, sizeof(ch[0]));
    }
    int idx(char c) {
        return c - 'a';
    }
    void insert(char *s, int v) {
        int u = 0, n = strlen(s);
        for (int i = 0; i < n; i++) {
            int c = idx(s[i]);
            if (!ch[u][c]) {
                memset(ch[sz], 0, sizeof(ch[sz]));
                val[sz] = 0;
                ch[u][c] = sz++;
            }
            u = ch[u][c];
        }
        val[u] = v;
    }
    void query(char *s, int x) {
        int u = 0, ans = 0;
        for (int i = x; i < len; i++) {
            int c = idx(s[i]);
            if (!ch[u][c]) return ;
            u = ch[u][c];
            if (val[u]) d[x] = (d[x] + d[i + 1]) % mod;
        }
    }
};
char w[110], str[300100];
Trie T;
int main () {
    int cnt = 1, n;
    while(~scanf("%s", str)) {
        len = strlen(str);
        scanf("%d", &n);
        T.init();
        for(int i = 0; i < n; i++) {
            scanf("%s", w);
            T.insert(w, 1);
        }
        d[len] = 1;
        for (int i = len - 1; i >= 0; i--) {
            d[i] = 0;
            T.query(str, i);
        }
        printf("Case %d: %d\n", cnt++, d[0]);
    }
    return 0;
}


联系
我们