UVA 1401 – Remember the Word [Trie]

点击打开UVa题目链接

题意

给出一个由S个不同单词组成的字典和一个长字符串。把这个字符串分解成若干个单词的连接(单词可以重复使用),有多少种方法?

分析

先找出递推的公式,然后用字典树查询单词是否出现再字典中。Trie的基础练手题。

C++代码

#include <bits/stdc++.h>
using namespace std;

struct Tire {
    static const int maxnode = 400000+10, sigma_size = 30;
    int ch[maxnode][sigma_size], val[maxnode], sz;
    Tire() { clear(); }
    void clear() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); val[0] = 0; }
    int idx(char x) { return x - 'a'; }

    void insert(const char *s, int v) {
        int u = 0;
        for(int i = 0; s[i] != 0; ++i) {
            int id = idx(s[i]);
            if(!ch[u][id]) {
                memset(ch[sz], 0, sizeof(ch[sz]));
                val[sz] = 0;
                ch[u][id] = sz++;
            }
            u = ch[u][id];
        }
        val[u] = v;
    }

    void query(const char *s, vector<int> &pos) {
        pos.clear();
        int u = 0;
        for(int i = 0; s[i] != 0; ++i) {
            int id = idx(s[i]);
            if(!ch[u][id]) return;
            else {
                u = ch[u][id];
                if(val[u]) pos.push_back(i);
            }
        }
    }
}tire;

const int maxn = 300005, maxm = 110, mod = 20071027;
int n, dp[maxn], len;
char t[maxm], s[maxn];
vector<int> pos;

int main() {
    int kase = 0;
    while(~scanf("%s", s)) {
        tire.clear();
        scanf("%d", &n);
        for(int i = 0; i < n; ++i) {
            scanf("%s", t);
            tire.insert(t, 1);
        }
        len = strlen(s);
        memset(dp, 0, sizeof(dp)); dp[len] = 1;
        for(int i = len-1; i >= 0; --i) {
            tire.query(s + i, pos);
            for(int j = 0; j < pos.size(); ++j)
                dp[i] = (dp[i] + dp[i+pos[j]+1]) % mod;
        }
        printf("Case %d: %d\n", ++kase, dp[0]);
    }
    return 0;
}

欢迎留言