C++中查找 S1 中在给定代价下与 S2 匹配的最长子串
内容提要
给定两个长度为n的字符串S1和S2，通过更改S1子串中的字符，使其与S2中的相应段匹配，且总成本最多为target。使用二进制搜索查找最大可能长度，时间复杂度为O(N*log(N))，辅助空间为O(1)。
延伸解读
二分搜索与滑动窗口的协同
文章采用二分搜索确定最大长度，对每个中间长度用滑动窗口检查是否存在成本不超过target的子串。这种组合将问题转化为判定性问题，使时间复杂度降至O(N log N)。滑动窗口在O(N)内计算所有固定长度子串的转换成本，与二分搜索的O(log N)层结合，高效且易于实现。
转换成本的计算方式
每个字符的转换成本固定为C，仅当S1和S2对应位置字符不同时才累加。滑动窗口移动时，通过减去离开窗口的字符成本、加上进入窗口的字符成本来维护当前窗口总成本，避免重复计算。这种增量更新保证了窗口检查的线性时间。
边界处理与输出
代码使用全局变量startPos和endPos记录有效子串的起止索引，初始化为-1。若二分搜索后startPos仍为-1，则输出“Not possible”，表示不存在满足条件的子串。否则输出任意一个最大长度的有效子串位置。注意二分搜索中end初始为字符串长度，且更新时end=mid而非mid-1，确保不漏掉可能长度。
Q&A
C++中如何查找S1中在给定代价下与S2匹配的最长子串？
使用二分搜索结合滑动窗口。二分搜索最大长度，对于每个中间长度，用滑动窗口检查S1中所有该长度的子串，计算转换成本是否不超过target。如果找到有效子串，则尝试更长长度；否则尝试更短长度。最终输出最长有效子串的起始和结束索引。
这个算法的时间复杂度和空间复杂度是多少？
时间复杂度为O(N*log(N))，辅助空间为O(1)。
转换成本是如何计算的？
对于子串中的每个字符，如果S1中的字符与S2中对应位置的字符不同，则成本增加C；如果相同，则成本增加0。总成本是所有字符转换成本之和。
如果存在多个相同最大长度的有效子串，应该返回哪一个？
可以返回其中任何一个。算法在找到第一个有效子串时就会记录其起始和结束位置，并继续搜索更大的长度，最终返回的是最大长度下的一个有效子串。
能否提供一个具体的输入输出示例？
例如：S1 = "abcd", S2 = "bcdf", C = 1, target = 3。输出为1 3，表示S1中索引1到3的子串"bcd"可以更改为"cdf"，成本为3，最大长度为3。
滑动窗口在算法中是如何工作的？
滑动窗口用于检查固定长度len的子串。初始化窗口左右指针i和j，右指针j遍历字符串，累加转换成本。当窗口大小达到len时，检查成本是否≤target，如果是则记录索引；然后左指针i右移，并减去移出字符的成本，继续滑动。
