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. ↵
↵
↵
↵
↵
↵
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. ↵
↵
↵
↵
↵
