LA 3942 Remember the Word

题意是给出S个不重复的单词组成的字典和一个长字符串，把这个字符串分解成若干个单词的连接，一共可以有多少中分割方法

很容易想到这样的DP，设T为长字符串，S(i)为T(i...L)也就是从i开始的T的后缀，f(i)为S(i)的切割种类数量的的话，可以有方程

f(i) = sum{f(j + 1)|T(i...j)∈字典) 边界为当f(L) = 1

那么需要做的工作就是，查找每个T(i...j)，看其是否在S个不重复的单词之中。

虽说T(i..j)的范围有300000,但是S中的每一个单词的长度只有100,所以将S中的所有单词建成一棵Trie，在其中查询，最坏情况的复杂度是300000 * 100，可以接受了

#include <cstdio>
#include <sstream>
#include <fstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <cctype>
#include <ctime>
#include <set>
#include <climits>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <cmath>
#include <string>
#include <list>

#define INPUT_FILE "in.txt"
#define OUTPUT_FILE "out.txt"

using namespace std;

typedef long long LL;
const int INF = INT_MAX / 2;

void setfile() {
    freopen(INPUT_FILE,"r",stdin);
    freopen(OUTPUT_FILE,"w",stdout);
}

const int maxlens = 300005;
const int maxlen = 105;
const int maxn = 4005;
const int maxnode = maxn * maxlen;
const int sigma_size = 26;
const int MOD = 20071027;

struct tnode {
    int next[sigma_size];
    bool exist;
};

tnode node[maxnode];
int sz;
int d[maxlens];
char buf[maxlens],tmp[maxlen];

void init() {
    sz = 1; memset(&node[0],0,sizeof(tnode));
}

inline int idx(char c) {
    return c - 'a';
}

void insert(char *str) {
    int u = 0,len = strlen(str);
    for(int i = 0;i < len;i++) {
        int c = idx(str[i]);
        if(node[u].next[c] == 0) {
            memset(&node[sz],0,sizeof(tnode));
            node[u].next[c] = sz++;
        }
        u = node[u].next[c];
    }
    node[u].exist = true;
}

int main() {
    int kase = 1;
    while(~scanf("%s",buf)) {
        memset(d,0,sizeof(d));
        init();
        int n; scanf("%d",&n);
        for(int i = 0;i < n;i++) {
            scanf("%s",tmp);
            insert(tmp);
        }
        int len = strlen(buf);
        d[len] = 1;
        for(int i = len - 1;i >= 0;i--) {
            int u = 0;
            for(int j = i;j < len;j++) {
                int c = idx(buf[j]);
                if(node[u].next[c] == 0) break;
                u = node[u].next[c];
                if(node[u].exist) {
                    d[i] = (d[i] + d[j + 1]) % MOD;
                }
            }
        }
        printf("Case %d: %d
",kase++,d[0]);
    }
    return 0;
}