3213. 最小代价构造字符串

题目描述：

给你一个目标字符串 target，一个字符串数组 words，以及一个对应的花费数组costs，每个word对应一个cost

你可以从words数组中选择任意数量的任意字符串，拼接起来，求拼接成target的最小花费

如果不能拼成target则输出-1

• 1 <= target.length <= 5 * 104
• 1 <= words.length == costs.length <= 5 * 104
• 1 <= words[i].length <= target.length
• 所有 words[i].length 的总和小于或等于 5 * 104
• target 和 words[i] 仅由小写英文字母组成。
• 1 <= costs[i] <= 104

思路

考虑动态规划，设状态$dp[i]$表示构造出$target$前$i$位的最小花费

状态转移方程：

• 假设$words[j]$能匹配$target[i]$到 $target[i+len_j-1]$，
• 则状态转移方程为 $dp[i+len_j+1] = min(dp[i+len_j+1], dp[i] + cost_j)$

所以我们需要想个对每个$word$求出在 $target$中所有匹配成功的位置，方便进行状态转移

正解是用后缀数组或者AC自动机来求，不过我不会，我用的字典树进行代替一下，解决匹配问题

但是，字典树最坏的情况会是$O(n^2)$，这次数据不够强，可以卡过去

class Solution {
public:
    int tr[50005][26];
    int tot;
    int val[50005];
    void add(string s, int c){
        int root = 0;
        for(int i = 0; i < s.size(); ++i){
            int id = s[i] - 'a';
            if(!tr[root][id])tr[root][id] = ++tot;
            root = tr[root][id];
        }
        if(val[root] == -1)val[root] = c;
        else val[root] = min(val[root], c);

    }
    int minimumCost(string target, vector<string>& words, vector<int>& costs) {
        tot = 0;
        memset(val, -1,sizeof(val));
        for(int i = 0; i < words.size(); ++i)
            add(words[i], costs[i]);
        vector<int>dp(target.size() + 1, 1e9);
        dp[0] = 0;
        for(int i = 0; i < target.size(); ++i){
            int root = 0;
            for(int j = i; j < target.size(); ++j){
                int id = target[j] - 'a';
                if(tr[root][id] == 0)break;
                root = tr[root][id];
                if(val[root] != -1){
                    dp[j + 1] = min(dp[j + 1], dp[i] + val[root]);
                }
            }
        }
        if(dp[target.size()] == 1e9)return -1;
        else return dp[target.size()];
    }
};

还有一种字符串哈希的方法，不过也不是正解

思路是，进行状态转移的时候，我们不是从 $i$ 枚举到$n$进行匹配，而是枚举可能的长度，统计一下所有$word$的长度，由于题目保证所有 words[i].length 的总和小于或等于 50000，所以最坏情况长度是1 2 3 4….，不同长度的字符串的数量最大是 $\sqrt{50000}$,最多就两百多不同长度的字符串，只需要枚举这个，然后想一个$O(1)$的方法获取长度为len的字符串中能匹配$target[i]$到 $target[i+len-1]$的字符串，这个可以用哈希来实现，对于每个长度，我们都开一个unordered_map存字符串的哈希值和费用，然后对$traget$也进行哈希处理，判匹配的时候就可以利用哈希O(1)计算

一个小技巧是，对于“体型”很大的stl结构需要多次遍历时，可以传引用参数，避免每次遍历都要复制一遍，跑的会快一些

比如，for(auto [len, x] : mp) 和 for(auto& [len, x] : mp)

1. for(auto [len, x] : mp)：

   这种写法会从容器 mp 中获取每对键值对（key-value pair），并对它们进行复制。也就是说，[len, x] 是对每个元素的拷贝。如果对 len 或 x 的修改不会影响到容器中原始的值。

2. for(auto& [len, x] : mp)：

   这种写法使用引用，因此不会对容器中的元素进行拷贝，而是直接引用容器中的元素。在这种情况下，[len, x] 是对容器中每个元素的引用。如果在循环体内修改 len 或 x，将直接修改容器中相应的值。

class Solution {
public:
    const int mod = 1070777777;
    const int base = 1331;
    int minimumCost(string target, vector<string>& words, vector<int>& costs) {
        int n = words.size(), m = target.size();
        vector<int>hs(m + 1), mul(m + 1);
        mul[0] = 1;
        for(int i = 1; i <= m; ++i){
            mul[i] = ((long long)mul[i - 1] * base)%mod;
            hs[i] = ((long long)hs[i - 1] * base + target[i - 1])%mod;
        }
        map<int, unordered_map<int, int>>mp;
        for(int i = 0; i < n; ++i){
            int len = words[i].size();
            long long h = 0;
            for(int j = 0; j < len; ++j)
                h = (h * base + words[i][j])%mod;
            if(!mp[len].count(h))
                mp[len][h] = costs[i];
            else
                mp[len][h] = min(mp[len][h], costs[i]);
        }
        vector<int>dp(m + 1, 1e9);
        dp[0] = 0;
        for(int i = 1; i <= m; ++i){
            for(auto& [len, x] : mp){
                int j = i + len - 1;
                if(j > m)break;
                long long h = ((long long)hs[j] - ((long long)hs[i - 1] * mul[len])%mod + mod) % mod;
                if(x.count(h)){
                    dp[j] = min(dp[j], dp[i - 1] + x[h]);
                }
            }
        }
        if(dp[m] == 1e9)return -1;
        else return dp[m];
    }
};