Need help in very interesting OA problem
Difference between en6 and en7, changed 13 character(s)
Many of my friends asked this interesting OA problem to me: ↵

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 contains exactly $B$ of the strings in $A$ as substring.↵

Return $D$ mod $10^9+9$.↵

Constraints↵

$1 \le N \le 6$↵

$1 \le |A[i]| \le 50$↵

All the $N$ strings are distinct↵

$0 \le B \le N$↵

$1 \le C \le 50.$↵

Note that if a substring belonging to set $A$ occurs multiple times in my resulting string, it is counted only once. ↵

My approach:↵

Let $Z$ be the size of the alphabet $(26)$.↵

Let $dp[i][j][k][m]$ denote the number of strings satisfying the constraints:↵

1) It is of length $i$.↵

2) The longest suffix present in it which is a proper prefix of some string belonging to set $A$ is the substring $[k...i]$ and the string whose proper prefix is the $j^{th}$ string in set $A$, in case of multiple such strings in $A$ choose the one with longest length. In case no such suffix exists, we can put a fake "empty string" at index $0$ in set $A$ (rest of the strings are numbered from $1$ to $N$) and assume that substring is $[i+1 , i]$.↵

3) The substrings (belonging to set $A$) which has already been occurred is denoted by mask $m$, more formally, if the $w^{th}$ string in $A$ has already occurred, then $w^{th}$ bit of $m$ is set, otherwise its not.↵

I'll write transitions via forward style dp, if I'm adding the $(i+1)^{th}$ character, then, it might "complete" some substrings, by this I mean, some suffix which was a proper prefix of some string in $A$ before adding character will now be a complete string belonging to set $A$. Note that all such strings will be the suffix of that longest suffix. ↵

So, some new bits in mask $m$ will be set, All this can be calculated, since we already know the longest suffix, in fact lets precalculate, $info[i][j][k]$ which gives a tuple $(bitmask, L, idx)$. If we consider the prefix of length $j$ of $i^{th}$ string in set $A$ and add character $k$ at the end, $w^{th}$ bit in bitmask is set iff, entire $w^{th}$ string in $A$ occurs as a substring in that prefix after adding character $k$, $L$ denotes the length of the longest suffix in resulting string (after adding character $k$) that is a proper prefix of $idx^{th}$ string in set $A$, this precomputation can be done naively in $O(N*C*Z*N)$. ↵

So, after adding $(i+1)^{th}$ character (denote it by $c$), new mask is $
 (m | info[j][i-k+1][c][0])$, new length of longest suffix is $info[j][i-k+1][c][1]$ so, add its contribution towards state $dp[i+1][info[j][i-k+1][c][3]][i+2-info[j][i-k+1][c][1]][(m | info[j][i-k+1][c][0])]$.↵

I think the complexity would be $O(C*N*C*2^{N}*Z)$, which might pass. However, I think I'm overkilling it and there has to be simpler solution. I'm not even sure whether my solution is correct or not. ↵




History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English ShivanshJ 2023-09-30 00:18:29 2 Tiny change: 'i-k+1][c][3]][i+2-inf' -> 'i-k+1][c][2]][i+2-inf'
en7 English ShivanshJ 2023-09-30 00:10:03 13
en6 English ShivanshJ 2023-09-30 00:08:07 13 (published)
en5 English ShivanshJ 2023-09-30 00:06:38 2 Tiny change: 'if the $w^th$ string i' -> 'if the $w^{th}$ string i'
en4 English ShivanshJ 2023-09-30 00:04:41 4
en3 English ShivanshJ 2023-09-30 00:04:16 84 Tiny change: '$D$ mod $1e^9+9$.\n\n' -> '$D$ mod $10^9+9$.\n\n'
en2 English ShivanshJ 2023-09-30 00:01:33 2370 Tiny change: 'e 50.$\n\n\n\n\n' -> 'e 50.$\n\nMy approach:\n\nLet $dp[i][j][k][mask]\n\n\n\n\n'
en1 English ShivanshJ 2023-09-29 23:17:20 439 Initial revision (saved to drafts)