【POJ，3320】Jessica，amp，39，s，Reading，Problemc(尺取法)

题目描述：

Jessica 拥有一个有 N 个字符的英文文本 T，他想知道其中所有的长度为 K 的不同连续子串（子串指原字符串中连续的一段字符组成的字符串）的个数。由于文本非常长，因此 Jessica 想要请求出你的帮助。

输入格式：

输入文件的第一行为三个取值范围在 1 到 10^5 之间的整数 N, K 和 Q，其中 N 表示文本 T 的长度，K 表示要查询的子串的长度，Q 表示询问的次数，注意有可能会有多个询问，其中 $1 \leq Q \leq $10^5。

输入文件的第二行为一个有 N 个字符组成的小写字母串 T，对于文本串中的每个字符，保证范围在'a'到'z'之间。

接下来 Q 行，每行两个整数 L 和 R 表示查询范围，即 Jessica 希望查询文本串 T[L,R] 中有多少不同的长度为 K 的子串。

输出格式：

输出文件应该包括 Q 行，每行为一个整数，按照询问的顺序排列，表示查询结果。

解题思路：

本题可使用双指针“尺取法”求解。

指针从字符串某一端依次向另一端，且在此过程中不借助其他数据结构，计算出子串等问题

本题目中，滑动窗口维护的是长度为 K 的串。每当滑动窗口向右滑动一位时，我们检查窗口内是否包含了一个长度为 K 的子串

我们使用cnt计数，记录长度为K的子串的数量。

每次移动右端点时，如果该点所在位置在该长度为K的窗口中有不存在的字符出现，cnt++；

当左端点移动时，如果左端点所在位置的字符仍在窗口中（没有重新出现），cnt--。

代码实现：

我们的目标是求出串T中的所有长度为K的不同连续子串的个数。我们可以In [1]中定义一个集合S，存储已经出现的所有长度为K的子串，最终答案即S的大小。然而考虑优化这个代码。

我们可以使用双指针“尺取法”求解。

我们可计算出答案（长度为K的子串的个数）的依据即是：“长度为K的子串，包含了长度为K+1的子串。”。

当我们记录某一时刻的长度为K的子串个数时，设该时刻的右端点为r，则：

$$ K_{r} = \sum_{i=1}^{T} [L_{i} \leq r , L_{i} > r-K] $$

其中，$L_{i}$为长度为K的子串左端点下标。上述式子的含义为，长度为K的子串有多少个满足其右端点为r。即，

若A也是长度为K的子串，则必满足$r - K + 1 \leq L_a \leq r$。

如果要求全局长度为K的子串个数，可以依次求出每个位置上的答案，最后相加。

由于每次右端点向右移动一位都只会影响到一个长度为K的子串（新的一个左端点进入或者原左端点消失），因此可以使用双指针“尺取法”求解该问题。

在移动右端点时，如果该点所在位置在该长度为K的窗口中有不存在的字符出现，cnt++；（在集合中加入一个新的长度为K的子串）

当左端点移动时，如果左端点所在位置的字符仍在窗口中（没有重新出现），cnt--。（从集合中删除一个长度为K的子串）

时间复杂度：O(n)

因为两个指针都只遍历了T，所以是线性算法。

空间复杂度：O(n)

需要开一个哈希表，存储每个长度为K的字符串。

参考代码：