jarvis_yash's blog

Need help to solve this proble
By jarvis_yash, history, 8 months ago, In English

Given an array of strings A of size N and two integers B and C Let D be the number of strings of length C that contain exactly B of the strings in words as substrings. Return D modulo (10+9).

|A|<=6 |A[i]|,C<=50 B<=N

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

original problem

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    u got solution for it ? ( it was asked in placement test )

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      if it was one string then we would have done dp with kmp but writing 6 kmp functions(in worst case) dont see me optimal in this case...i am also curious for the approach

      → Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    .

    → Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Here's a brute force approach using dfs. not sure if it will suffice

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

const int MOD = 1e9 + 9;

int dfs(string curr_str, vector<string> &A, int B, int C)
{
	if (curr_str.size() == C)
	{
		int count = 0;
		for (auto &s : A)
		{
			if (curr_str.find(s) != string::npos)
			{
				count++;
			}
		}
		return count == B ? 1 : 0;
	}

	int total = 0;
	for (char ch = 'a'; ch <= 'z'; ++ch)
	{
		total += dfs(curr_str + ch, A, B, C);
		total %= MOD;
	}

	return total;
}

int required_substrings(vector<string> &A, int B, int C)
{
	return dfs("", A, B, C);
}

int main()
{
	vector<string> A = {"z", "zz", "zzz", "zzzz"};
	int B = 2;
	int C = 3;
	cout << required_substrings(A, B, C) << endl; // Expected output: 50
	return 0;
}

Your code here...
→ Reply