CF1276F Asterisk Substrings

Consider a string $ s $ of $ n $ lowercase English letters. Let $ t_i $ be the string obtained by replacing the $ i $ -th character of $ s $ with an asterisk character \*. For example, when $ s = \mathtt{abc} $ , we have $ t_1 = \tt{*bc} $ , $ t_2 = \tt{a*c} $ , and $ t_3 = \tt{ab*} $ . Given a string $ s $ , count the number of distinct strings of lowercase English letters and asterisks that occur as a substring of at least one string in the set $ \{s, t_1, \ldots, t_n \} $ . The empty string should be counted. Note that \*'s are just characters and do not play any special role as in, for example, regex matching.

N/A

N/A

For the sample case, the distinct substrings are (empty string), a, b, c, \*, ab, a\*, bc, b\*, \*b, \*c, abc, ab\*, a\*c, \*bc.