A very interesting OA problem

Revision en5, by ShivanshJ, 2023-09-30 00:06:38

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 $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]][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 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 ShivanshJ 2023-09-30 00:10:03 13
en6 ShivanshJ 2023-09-30 00:08:07 13 (published)
en5 ShivanshJ 2023-09-30 00:06:38 2 Tiny change: 'if the $w^th$ string i' -> 'if the $w^{th}$ string i'
en4 ShivanshJ 2023-09-30 00:04:41 4
en3 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 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 ShivanshJ 2023-09-29 23:17:20 439 Initial revision (saved to drafts)