Summary

This problem can be solved by the following steps.

1. Construct the Suffix Array (SA) and Longest Common Prefix (LCP) Array (LA) for a string obtained by concatenating \(S\), \(T_1\), \(\ldots\), and \(T_N\).
2. For \(i=1,2,\ldots,|S|\), find a substring of \(S\) starting from the \(i\)-th character that coincides with any of \(T_1,\ldots,T_N\) with the smallest length.
3. Find the minimum number of operations required, subject to that every \([l_1,r_1], [l_2,r_2], \ldots\) contains at least one *.

Constructing SA and LA

We first construct a string \(X\) that contains \(S, T_1, \ldots, T_N\) as its substrings. For example, for Sample Input 1, \(X\) will be like abcdefghijklmn_abcd_ijk_ghi (although it depends on approaches, it is recommended to add a separator). Then, we construct the SA and LA of this string. It is implemented in ACL (AtCoder Library), so we recommend you to read the document first if you are not used to it.
Here, we prove a property of LA that we use later. As in the document, LA is an array that expresses the LXP of the two prefixes adjacent on SA. Also, for two prefixes that are not necessarily adjacent on SA, the LCP is the minimum value of the values in the corresponding segment of LA. Thus, by storing it on a segment tree that supports segment minimum value, we can find the LCP of any pair of prefixes. Moreover, by applying this fact for \(X\) we constructed this time, we can check if a substring starting from the \(j\)-th character of \(S\) coincides with \(T_i\).

Determining how many characters of \(S\) starting from the \(i\)-th character coincides with \(T_i\)

For example, when \(S=\) abc, \(T_1=\) ab, and \(T_2=\) abc, the first through second characters of \(S\) coincides with \(T_1\), and from first through third to \(T_2\). Here, obviously, once any of the first through second characters is replaced with * to hide \(T_1\), \(T_2\) is hidden too. Thus, for \(i=1,2,\ldots,|S|\), among the substrings starting from the \(i\)-th character starting from \(T_i\), it is sufficient to consider one with the smallest length.
In order to find the minimum length of such substring, we may use LA as follows:

• Initialize a balanced binary tree with all the positions on the SA stored.
• For \(T_1,\ldots,T_N\), process in ascending order of \(|T_i|\):
  • Binary search on the segment tree containing the LA to find the segment on SA corresponding to those with a prefix coinciding with \(T_i\).
  • Extract the values contained in the obtained segment from the set, record as \(|T_i|\) the length of \(T_i\) contained as the first part of the prefix, and remove these values from the set.

Alternatively, we may perform a segment update on a lazy segment tree in descending order of \(|T_i|\).

Finding the minimum number of operations that covers all segments

With all the process so far, the problem is boiled down to: “for at most \(|S|\) segments, we want to make each of them contain at least one * by performing the operation some number of times. How many operations is required at minimum?” This can be solved by sorting by the right end and do a greedy simulation. (Reference: past problem that is almost the same as this part)