給定一個模式串,有若干個單詞,問是否能用若干個單詞組合,組合成模式串

ICPC-2007 Asia regional - Nanjing

題目鏈接
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=282&page=show_problem&problem=1943

思路:這種有后綴類型的題目一開始還以為是后綴數(shù)組缅刽，然后仔細(xì)想了一下雕欺，后綴數(shù)組更多的是解決兩個大的模式串之間產(chǎn)生的后綴之間的關(guān)系，而這個實際上是要把一堆小的零散的單詞拼湊成一個大的模式串，所以給用第二種匹配方法．劉老師說這個超棒的
首先給明白一個遞推關(guān)系，實際上我們可以直接從最后出發(fā)，命名一個dp數(shù)組,推出狀態(tài)轉(zhuǎn)移方程即dp[i] = dp[i +len(x)] + dp[i]
認(rèn)為dp[i]實質(zhì)上是為組成以i開始到總長度的組成反感,x實際上就是i到總長度這個子串的長度
那么解法就可以出來了
我們將所有出現(xiàn)的單詞壓入字典樹
倒著遍歷一遍,因為不限制單詞重復(fù)使用,所以我們可以將所有適合的方案全部壓入對應(yīng)的后綴之中,然后相應(yīng)修改匹配模塊即可

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<set>


using namespace std;
const int maxnode = 4000 * 100 + 10;
const int sigma_size = 26;
const int maxl = 300000 + 10;
const int maxw = 4000 + 10;
const int maxwl = 100 + 10;
const int MOD = 20071027;

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';
    }

    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;
                ch[u][c] = sz ++;
            }
            u = ch[u][c];
        }
        val[u] = v;
    }
    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]);
        }
    }
};


int d[maxl], len[maxw], S;
char text[maxl], word[maxwl];
Trie trie;

int main(){
    int kase = 1;
    while (~scanf("%s%d", text, &S)){
    //  printf("%d\n", S);
        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;
}