CSES Word Combination(字典树,DP)

(Updated: )
算法 › 字符串

CSES Word Combination(字典树,DP)

题意

给定一个字符串s, 给$n$个单词, 问:
这个字符串可以被这些单词组合成多少种方式?

题解

使用dp思想解决有多少种组合, 使用trie来快速匹配单词

  1. 定义状态dp[i]表示前i个字符可以被这些单词组合成多少种方式
  2. 初始化dp[0] = 1
  3. 状态转移: 如果dp[i] != 0说明有以第i个字符结尾的单词, 那么就查找可以从i之后出发的单词在i+1到j之间, 那么dp[j+1] = (dp[j+1] + dp[i]) % M;
  4. 返回dp[s.size()]

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define i128 __int128

#define DEBUG
#ifdef DEBUG
#define de(x) cout << (#x) << " = " << (x) << endl;
#define de2(x, y) cout << (#x) << " , " << (#y) << " = " << (x) << " ~ " << (y) << endl;
#else
#define de(x)
#define de2(x, y)
#endif
#define enld endl
#define endl '\n'
#define fi(x) for(int i = 1; i <= x; ++i)
#define fi0(x) for(int i = 0; i < x; ++i)
#define fj(n) for(int j = 1; j <= n; ++j)
#define caillo ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PLEASE_AC return 0
typedef long long ll;
typedef unsigned long long ull;
// #define int long long


const int N = 1e6 + 10;
const int M = 1e9 + 7;
int node[N][26], idx;  //节点和节点编号
bool isEnd[N];

void insert(const string &s) {  //插入单词
    int p = 0;
    for(int i = 0; i < s.size(); ++i) {  //遍历单词的每个字符
        int ch = s[i] - 'a';
        if(!node[p][ch]) node[p][ch] = ++idx;   //如果当前节点没有这个字符，就新建一个节点
        p = node[p][ch];  //更新当前节点
    }
    isEnd[p] = true;  //标记单词结束
}

int dp[N];
signed main() {
    caillo;
    string s; cin >> s;
    int n; cin >> n;
    fi(n) {
        string t; cin >> t;
        insert(t);
    }

    dp[0] = 1;
    for(int i = 0;i < s.size(); ++i) {
        if(!dp[i]) continue;
        int p = 0;
        for(int j = i;j < s.size(); ++j) {
            int ch = s[j] - 'a';
            if(!node[p][ch]) break;

            p = node[p][ch];
            if(isEnd[p]) dp[j+1] = (dp[j+1] + dp[i]) % M;
        }
    }

    cout << dp[s.size()] << endl;
}