LA3942 Remember the Word 背单词（Trie树+DP）

柔光的暖阳◎ 2021-12-11 14:03 236阅读 0赞

## 题意：给出一个由S个不同的字符串组成的字典和一个长字符串，问：把这个长字符串分解成若干个字典中出现的字符串，共有几种分法。单词可以重复使用。 ##

## 分析：详见《训练指南》P209-210，令d(i)表示从字符i开始的字符串(即后缀S\[i...L\])的分解方案数，那么d(i)=d(i+len(x)|单词x是S\[i..L\]的前缀)。如果我们枚举单词，然后判断它是否为S\[i...L\]的前缀，时间无法承受。所以可以考虑事先把所有的单词存入Trie，然后试着在Trie中查找S\[i...L\]。查找时，如果找到了一个单词结点，就把它的序号记下来，这样就找到了一个单词x，最多只需要100次比较就能找到所有的x。 ##

## 代码（LRJ）： ##

#include<cstring>
    #include<vector>
    using namespace std;
    
    const int maxnode = 4000 * 100 + 10;
    const int sigma_size = 26;
    
    // 字母表为全体小写字母的Trie
    struct Trie {
      int ch[maxnode][sigma_size];
      int val[maxnode];
      int sz; // 结点总数
      void clear() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); } // 初始时只有一个根结点
      int idx(char c) { return c - 'a'; } // 字符c的编号
    
      // 插入字符串s，附加信息为v。注意v必须非0，因为0代表“本结点不是单词结点”
      void insert(const 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;  // 中间结点的附加信息为0
            ch[u][c] = sz++; // 新建结点
          }
          u = ch[u][c]; // 往下走
        }
        val[u] = v; // 字符串的最后一个字符的附加信息为v
      }
    
      // 找字符串s的长度不超过len的前缀
      void find_prefixes(const char *s, int len, vector<int>& ans) {
        int u = 0;
        for(int i = 0; i < len; i++) {
          if(s[i] == '\0') break;
          int c = idx(s[i]);
          if(!ch[u][c]) break;
          u = ch[u][c];
          if(val[u] != 0) ans.push_back(val[u]); // 找到一个前缀
        }
      }
    };
    
    #include<cstdio>
    const int maxl = 300000 + 10; // 文本串最大长度
    const int maxw = 4000 + 10;   // 单词最大个数
    const int maxwl = 100 + 10;   // 每个单词最大长度
    const int MOD = 20071027;
    
    int d[maxl], len[maxw], S;
    char text[maxl], word[maxwl];
    Trie trie;
    
    int main() {
      int kase = 1;
      while(scanf("%s%d", text, &S) == 2) {
        trie.clear();
        for(int i = 1; i <= S; i++) {
          scanf("%s", word);
          len[i] = strlen(word);
          trie.insert(word, i);
        }
        memset(d, 0, sizeof(d));
        int L = strlen(text);
        d[L] = 1;
        for(int i = L-1; i >= 0; i--) {
          vector<int> p;
          trie.find_prefixes(text+i, L-i, p);
          for(int j = 0; j < p.size(); j++)
            d[i] = (d[i] + d[i+len[p[j]]]) % MOD;
        }
        printf("Case %d: %d\n", kase++, d[0]);
      }
      return 0;
    }