给定一个原始文本字符串 � ∣�∣≤3×105S ∣S∣≤3×10 5 和一个有用信息字符串 � ∣�∣≤200T ∣T∣≤200现在可以对 �S 进行精简操作具体来说就是可以将 �S 的开头和结尾分别去掉一段使得剩下的字符串 �′S ′ 中包含有有用信息 �T。 请问有多少种精简 �S 的方式？

可以使用双指针来解决这个问题。我们分别用指针 � i 和 � j 来表示 � S 的开头和结尾。一开始，它们分别指向字符串的第一个字符和最后一个字符。

我们从指针 � i 开始向右移动，直到 � S[i:j+1] 包含了所有的有用信息 � T 中的字符。然后，我们从指针 � j 开始向左移动，直到 � S[i:j+1] 不再包含所有的有用信息 � T 中的字符。

在这个过程中，我们可以记录下所有满足条件的 � S[i:j+1]，它们的数量就是答案。

时间复杂度

指针最多移动 � 2∣S∣ 次，因此时间复杂度为 � O(∣S∣)。

C++ 代码