Word Combinations

You are given a string of length n and a dictionary containing k words. In how many ways can you create the string using the words?

Example:

Input:  s = "ababc", m = 4, arr = {"ab", "abab", "c", "cb"}
Output: 2

Approach

C++

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const long long MAX_S = 1e6;
const long long MAX_C = 26;

long long tr[MAX_S][MAX_C], cnt[MAX_S], num;

void insert(string t)
{
    long long u = 0;
    for (char c : t)
    {
        if (!tr[u][c - 'a'])
            tr[u][c - 'a'] = ++num;
        u = tr[u][c - 'a'];
    }
    cnt[u]++;
}

long long wordCombinations(string s, long long m, 
                            vector<string> &arr)
{

    long long n = s.size();
    for (long long i = 0; i < m; i++)
    {

        insert(arr[i]);
    }
    vector<long long> dp(n + 1);
    dp[0] = 1;
    for (long long i = 0; i < n; i++)
    {
        long long u = 0, len = 1;
        for (char c : s.substr(i))
        {
            if (!tr[u][c - 'a'])
                break;
            u = tr[u][c - 'a'];
            if (cnt[u])
                dp[i + len] = (dp[i + len] + dp[i]) % MOD;
            len++;
        }
    }
    return dp[n];
}

int main()
{
    string s = "ababc";
    long long m = 4;

    vector<string> arr = {"ab", "abab", "c", "cb"};

    cout << wordCombinations(s, m, arr) << "\n";

    return 0;
}