class Solution:
    def getEncryptedString(self, s: str, k: int) -> str:
        return s[k % len(s):] + s[0: k % len(s)]

class Solution:
    def validStrings(self, n: int) -> List[str]:
        ans = []
        mask = (1 << n) - 1
        for i in range(1 << n):
            x = mask ^ i
            if (x >> 1) & x == 0:
                ans.append(f"{i:0{n}b}")
        return ans

class Solution:
    def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        res = 0
        dp1 = [[0] * (n + 1) for _ in range(m + 1)]
        dp2 = [[0] * (n + 1) for _ in range(m + 1)]
    
        for i in range(m):
            for j in range(n):
                dp1[i + 1][j + 1] = dp1[i][j + 1] + dp1[i + 1][j] - dp1[i][j]
                dp2[i + 1][j + 1] = dp2[i][j + 1] + dp2[i + 1][j] - dp2[i][j]
                if grid[i][j] == 'X':
                    dp1[i + 1][j + 1] += 1
                if grid[i][j] == 'Y':
                    dp2[i + 1][j + 1] += 1
                if dp1[i + 1][j + 1] > 0 and dp1[i + 1][j + 1] == dp2[i + 1][j + 1]:
                    res += 1
         
        return res

class Solution {
public:
    static constexpr long long mod = 1e9 + 7;
    static constexpr long long base = 31;
    int minimumCost(string target, vector<string>& words, vector<int>& costs) {
        int n = target.size();
        vector<long long> hbase(n + 1, 1);
        vector<long long> pre(n + 1);
        for (int i = 0; i < n; i++) {
            hbase[i + 1] = hbase[i] * base % mod;
            pre[i + 1] = (pre[i] * base + target[i] - 'a') % mod;
        }

        /* 计算当前长度的哈希值 */
        auto get = [&](int pos, int len) -> long long {
            return (pre[pos] - (pre[pos - len] * hbase[len] % mod) + mod) % mod;
        };

        map<int, unordered_map<long long, int>> cnt;
        for (int i = 0; i < words.size(); i++) {
            long long cur = 0;
            int len = words[i].size();
            for (char c : words[i]) {
                cur = (cur * base + c - 'a') % mod;
            }
            if (cnt[len].find(cur) != cnt[len].end()) {
                cnt[len][cur] = min(cnt[len][cur], costs[i]);
            } else {
                cnt[len][cur] = costs[i];
            }
        }
        
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (auto &[len, mp] : cnt) {
                if (len > i) break;
                if (dp[i - len] == INT_MAX) continue;
                long long key = get(i, len);
                if (mp.count(key)) {
                    dp[i] = min(dp[i], dp[i - len] + mp[key]);
                }
            }
        }

        return dp[n] == INT_MAX ? -1 : dp[n];
    }
};

struct Node {
    Node* son[26]{};
    Node* fail; // 当 cur.son[i] 不能匹配 target 中的某个字符时，cur.fail.son[i] 即为下一个待匹配节点（等于 root 则表示没有匹配）
    Node* last; // 后缀链接（suffix link），用来快速跳到一定是某个 words[k] 的最后一个字母的节点（等于 root 则表示没有）
    int len = 0;
    int cost = INT_MAX;
};

struct AhoCorasick {
    Node* root = new Node();

    void put(string& s, int cost) {
        auto cur = root;
        for (char b : s) {
            b -= 'a';
            if (cur->son[b] == nullptr) {
                cur->son[b] = new Node();
            }
            cur = cur->son[b];
        }
        cur->len = s.length();
        cur->cost = min(cur->cost, cost);
    }

    void build_fail() {
        root->fail = root->last = root;
        queue<Node*> q;
        for (auto& son : root->son) {
            if (son == nullptr) {
                son = root;
            } else {
                son->fail = son->last = root; // 第一层的失配指针，都指向根节点 ∅
                q.push(son);
            }
        }
        // BFS
        while (!q.empty()) {
            auto cur = q.front();
            q.pop();
            for (int i = 0; i < 26; i++) {
                auto& son = cur->son[i];
                if (son == nullptr) {
                    // 虚拟子节点 cur.son[i]，和 cur.fail.son[i] 是同一个
                    // 方便失配时直接跳到下一个可能匹配的位置（但不一定是某个 words[k] 的最后一个字母）
                    son = cur->fail->son[i];
                    continue;
                }
                son->fail = cur->fail->son[i]; // 计算失配位置
                // 沿着 last 往上走，可以直接跳到一定是某个 words[k] 的最后一个字母的节点（如果跳到 root 表示没有匹配）
                son->last = son->fail->len ? son->fail : son->fail->last;
                q.push(son);
            }
        }
    }
};

class Solution {
public:
    int minimumCost(string target, vector<string>& words, vector<int>& costs) {
        AhoCorasick ac;
        for (int i = 0; i < words.size(); i++) {
            ac.put(words[i], costs[i]);
        }
        ac.build_fail();

        int n = target.size();
        vector<int> f(n + 1, INT_MAX / 2);
        f[0] = 0;
        auto cur = ac.root;
        for (int i = 1; i <= n; i++) {
            cur = cur->son[target[i - 1] - 'a']; // 如果没有匹配相当于移动到 fail 的 son[target[i-1]-'a']
            if (cur->len) { // 匹配到了一个尽可能长的 words[k]
                f[i] = min(f[i], f[i - cur->len] + cur->cost);
            }
            // 还可能匹配其余更短的 words[k]，要在 last 链上找
            for (auto match = cur->last; match != ac.root; match = match->last) {
                f[i] = min(f[i], f[i - match->len] + match->cost);
            }
        }
        return f[n] == INT_MAX / 2 ? -1 : f[n];
    }
};